[9.19模拟赛]最小粒子数

Description

有(n)个神奇的粒子团排成一列，第(i)个粒子团包含(a[i])个粒子， 若(a[i])为正，则表示这个粒子团包含了(a[i])个正粒子，否则包含了(-a[i])个反粒子，现在科学家格里梅尔想取出连续若干个粒子团， 使得这几个团合在一起后剩下的粒子数最少（一对正反粒子会湮灭）。
另外，格里梅尔希望在满足上述条件情况下，取出尽量多的粒子团。

Input

第一行输入(N)，表示粒子团的个数。接下来(N)行描述(a[i])。

Output

第一行输出一个整数，表示最少粒子的数量，第二行包含一个整数表示最多的粒子团。

Sample Input

8
-2
0
90
-30
-20
80
-70
-60
125

Sample Output

5 3

数据说明

(40)%的数据(N<=4000)
对于许多数据，最长序列的长度唯一。
(100)%的数据(N<=100000),(|)每个数字的值(|<=10^{10})

Solution

求出前缀和，按前缀和从小到大排序，去重，每次判断相邻两个数的差，求出答案
为了防止前缀和为0的情况，可以把前缀和也和答案比较

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define MAXN 200010
struct rec {
	ll sum, id;
} t[MAXN];
ll n, Max, l, r, ans;
inline ll read() {
	ll s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}
inline bool cmp(rec x, rec y) {
	return x.sum < y.sum;
}
int main() {
	freopen("min.in", "r", stdin);
	freopen("min.out", "w", stdout);
	n = read();
	for (register int i = 1; i <= n; i++)
		t[i].sum = t[i - 1].sum + read(), t[i].id = i;
	sort(t + 1, t + n + 1, cmp);
	Max = max(abs(t[1].sum), abs(t[n].sum));
	r = 1;
	l = 1;
	while (r <= n) {
		r++;
		if (abs(t[r].sum - t[l].sum) < Max) {
			Max = abs(t[r].sum - t[l].sum), ans = abs(t[r].id - t[l].id);
			continue;
		}
		if (abs(t[r].sum - t[l].sum) == Max) {
			ans = max(ans, abs(t[r].id - t[l].id));
			continue;
		}
		while (abs(t[r].sum - t[l].sum) > Max && l < r) l++;
		if (l == r) continue;
		if (abs(t[r].sum - t[l].sum) < Max) {
			Max = abs(t[r].sum - t[l].sum), ans = abs(t[r].id - t[l].id);
			continue;
		}
		if (abs(t[r].sum - t[l].sum) == Max) {
			ans = max(ans, abs(t[r].id - t[l].id));
			continue;
		}
	}
	for (register int i = 1; i <= n; i++) {
		if (abs(t[i].sum) < Max)
			Max = abs(t[i].sum), ans = t[i].id;	
		if (abs(t[i].sum) == Max)
			Max = abs(t[i].sum), ans = max(ans, t[i].id);	
	}
	printf("%lld
", Max);
	printf("%lld", ans);
	return 0;
}