链接:https://ac.nowcoder.com/acm/contest/949/D
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

水果店里有 nn个水果排成一列。店长要求顾客只能买一段连续的水果。
小阳对每个水果都有一个喜爱程度 aiai,最终的满意度为他买到的水果的喜欢程度之和。
如果和为正(不管是正多少,只要大于 00 即可),他就满意了。

小阳想知道在他满意的条件下最多能买多少个水果。

你能帮帮他吗?

输入描述:

第一行输入一个正整数 n,表示水果总数。

第二行输入 n 个整数 aiai,表示小阳对每个水果的喜爱程度。

输出描述:

一行一个整数表示结果。(如果 1 个水果都买不了,请输出 0)
示例1

输入

5
0 0 -7 -6 1

输出

1

备注:

1≤n≤2×106,|ai|≤1031≤n≤2×106,|ai|≤103

解题思路:把前缀和从小到大排序,如果前缀和相等把编号大的放前面,然后从前往后遍历,记录遍历过程最小的编号,如果当前的编号大于最小的编号,则更新答案。注意特判n=1的情况就可以了
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+;
int n;
struct node{
int pos,num;
}p[maxn];
bool cmp(node a,node b){
if(a.num==b.num) return a.pos>b.pos;
return a.num<b.num;
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
p[i].num=p[i-].num+x;
p[i].pos=i;
}
n++;
int minpos=n;
int ans=;
sort(p+,p+n+,cmp);
for(int i=;i<=n;i++){
minpos=min(minpos,p[i].pos); //记录编号最小的位置
if(minpos<p[i].pos) //当前编号大于记录的最小编号,则更新答案
ans=max(ans,p[i].pos-minpos);
}
printf("%d\n",ans);
return ;
}
05-11 20:18