牛客小白月赛19 D题 小阳买水果

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

小阳买水果

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述

水果店里有 n个水果排成一列。店长要求顾客只能买一段连续的水果。 小阳对每个水果都有一个喜爱程度 ai，
最终的满意度为他买到的水果的喜欢程度之和。 如果和为正（不管是正多少，只要大于 0 即可），他就满意了。
小阳想知道在他满意的条件下最多能买多少个水果。 你能帮帮他吗？

输入描述:

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

第二行输入 n 个整数 a i ai，表示小阳对每个水果的喜爱程度。

输出描述:

一行一个整数表示结果。（如果 1 个水果都买不了，请输出 0）

示例1

输入

5
0 0 -7 -6 1

输出

1

备注:

1≤n≤2×10e6

|ai|≤10e3

先上代码

//MADE BY Y_is_sunshine;
//#include <bits/stdc++.h>
//#include <memory.h>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define INF 0x3f3f3f3f
#define MAXN 2000005

using namespace std;

struct node {
	int sum;
	int pos;
	node() {
		sum = 0;
		pos = 0;
	}
}a[MAXN];

bool cmp(node x, node y) {
	if (x.sum == y.sum)
		return x.pos > y.pos;
	return x.sum < y.sum;
}

int main()
{
	//freopen("data.txt", "r", stdin);
	
	int N;
	cin >> N;
	
	for (int i = 1; i <= N; i++) {
		int b;
		scanf("%d", &b);
		a[i].sum = a[i - 1].sum + b;
		a[i].pos = i;
	}
	
	N++; a[N].pos = a[N].sum = 0;
	sort(a + 1, a + N + 1, cmp);

	int ans = 0;
	int last = N;

	for (int i = 1; i <= N; i++) {
		last = min(last, a[i].pos);
		if (last < a[i].pos)
			ans = max(ans, a[i].pos - last);
	}

	cout << ans << endl;

	//freopen("CON", "r", stdin);
	system("pause");
	return 0;
}

看不懂吧 我就知道~
开始解释~
首先排序按照前pos项和的大小排序
什么意思呢 这是让我们最后维护ans的时候后面要用的数一定覆盖前面的数
好吧听不懂
就是说如果1~5的和是 -5 1~7的和是-3
那么5~7一定是符合要求的一段区间

讲一下last的维护
如果1~6的值=-4
并且1-3的值是-3
那是不是last就可以等于3 然后后面的a[i].pos-last会更高并且符合题意

cmp的排序为什么当sum相等的时候按照地址从大到小排序？

显然 a-b是不符合条件的 ==0嘛
那么你最先就不能用小的地址去更新last的值

细心地童鞋是不是已经发现学会了前面的还过不去
sort上面还有一行。。。
当所有数据都是1的时候
a[i].sum=i;ans=a[i].pos-a[i-1].pos+1;

就酱紫~