題目連結:1065
題目上說的子序列就是子串---------------N個整數組成的序列a[1],a[2],a[3],…,a[n],從中選出一個子序列(a[i],a[i+1],…a[j]),
我們将0-i區間的和記為he [i] ,
貪心的核心--就是排序
然後我們講he排序--
判斷兩個和之間的差----(但是不要讓he[i]-he[j]----------( j < i ) 是以我們要加一個判斷)
設和開始為A B C D E
按大小排過以後是B D E A C
B--D,D--E A--C 之差都可以-- E--A之間的差不可以--因為A--E是(shu[2]+shu[3]+shu[4]+shu[5])的相反數。
這樣會不會丢失最優解??
不會。
題目有解--
是以排完後的序列至少有一個是i+1>i的
不會出現EDCBA且(都為負(不都為負時--我們在算He時已取he的最小值(kai=0;jie=i的情況)))的情況
隻要出現像E D A B C
如果B C之差最小--((C-B)<(B - A)<= (C-A) )
它一定是最優的--
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
LL a,ans,dd[50500];
struct node
{
LL ss;
int hao;
}he[50500];
bool cmp1(node xx,node yy)
{
return xx.ss<yy.ss;
}
int main()
{
int n;scanf("%d",&n);
he[0].ss=0;ans=999999999999999999;
for (int i=1;i<=n;i++)
{
scanf("%lld",&a);
he[i].ss=he[i-1].ss+a;
he[i].hao=i;
if (he[i].ss>0)
ans=min(ans,he[i].ss);
}
sort(he+1,he+n+1,cmp1);
for (int i=1;i<n;i++)
if (he[i+1].ss>he[i].ss&&he[i+1].hao>he[i].hao)
ans=min(he[i+1].ss-he[i].ss,ans);
printf("%lld\n",ans);
return 0;
}