题目链接: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;
}