【牛客网】 小白月赛16 D小阳买水果

题目链接：https://ac.nowcoder.com/acm/contest/949/D

题意：寻找最长的连续序列，满足序列和大于0.

题解：按照前缀和的大小排序，可以保证后面的一定大于等于前面（即区间和大于等于0），只需要选取满足条件的最左边的结点即为最大区间。

/*
题解：按照前缀和的大小排序，可以保证后面的一定大于等于前面（即区间和大于等于0），只需要选取满足条件的最左边的结点即为最大区间。
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
struct node
{
	int sum,id;
}a[maxn];
int cmp(node a,node b)
{
	if(a.sum==b.sum)
		return a.id>b.id;
	return a.sum<b.sum;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int temp;
		scanf("%d",&temp);
		a[i].sum=a[i-1].sum+temp;	//前缀和 
		a[i].id=i;
	}
	a[0].sum=a[0].id=0;				//一个数都不选择 
	sort(a,a+n+1,cmp);				//排序 
	int l=n,ans=0;					//l：取的起点 ans：答案 
	for(int i=0;i<=n;i++)
	{
		l=min(l,a[i].id);			//l：选取尽可能靠近左边的 
		ans=max(ans,a[i].id-l);		//更新答案 
	} 
	printf("%d\n",ans);
	return 0;
}