L. Lemper Cooking Competition(前缀和/逆序对/树状数组/归并排序)

题目
参考

题意

给定一个长度为n的整数数组a。每次可以做如下操作。

• 选择下标i, 1 < i < n
• 令a[i-1] += a[i];a[i+1] += a[i]; a[i] = -a[i]。

问最少需要多少次操作，才能使数组a所有元素都非负。如果不能做到，则输出-1。

思路

a[i] = -a[i]，实际上等价于a[i] -= 2*a[i]。
令pre[i] = a[1] + a[2] + … + a[i]。

如果我们操作了下标x，那么对于i <= x-2，pre的值不受影响。对于i >= x + 1，pre的值也不受影响。
而pre[x-1] +=a[x]，pre[x] -= a[x]。
等价于pre[x], pre[x-1] = pre[x-1], pre[x]。

所以，每次操作，等价于选择下标1

要使a所有元素非负，等价于前缀和数组pre所有元素非负，且有序。
因此0

如果存在最小元素<0（不能满足所有元素非负），或者中间元素pre[i]>pre[n]（此时第n个元素为负），此时无解。

有解的场景，就是求前缀和数组pre的逆序对的个数。

求数组的逆序对个数，可以用归并排序；也可以用树状数组、线段树。

归并排序

#include
using namespace std;
#define ll long long
const int maxn = 200010;
#define inf 1e18

int n;
ll c[maxn], a[maxn], b[maxn];

void print_a(string s) {
	printf("%s", s.c_str());
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", c[i]);
	}
	printf("\n");
}
// 归并排序 求逆序对
ll merge_sort(int l, int r) {
	if (l + 1 >= r) return 0;
	int m = (l + r) / 2;
	ll res = 0;
	res += merge_sort(l, m);
	res += merge_sort(m, r);
	for (int i = l; i < m; ++i) {
		a[i] = c[i];
	}
	for (int i = m; i < r; ++i) {
		b[i] = c[i];
	}
	int i = l, j = m, k = l;
	while (i < m && j < r) {
		if (a[i] <= b[j]) { // 为了求逆序对，注意这里的<= 不能用<
			c[k++] = a[i];
			++i;
		} else {
			c[k++] = b[j];
			res += m - i;
			++j;
		}
	}
	while (i < m) {
		c[k++] = a[i];
		++i;
	}
	while (j < r) {
		c[k++] = b[j];
		++j;
	}
	return res;
}


void solve() {
	scanf("%d", &n);
	c[0] = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &c[i]);
		c[i] += c[i-1];
	}
//	print_a("before sort");
	for (int i = 1; i <= n; ++i) {
		if (c[i] < 0 || c[i] > c[n]) {
			printf("-1\n");
			return;
		}
	}
	ll res = merge_sort(1, n + 1);
//	print_a("after sort");
	printf("%lld\n", res);
}

int main() {
	int t;
//	scanf("%d", &t);
	t = 1; 
	while (t--) {
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

树状数组

#include
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
const int maxn = 200010;
#define inf 1e18

int n;
ll a[maxn];
int c[maxn];

void print_a(string s) {
	printf("%s", s.c_str());
	for (int i = 1; i <= n; ++i) {
		printf("%lld ", a[i]);
	}
	printf("\n");
}
// 树状数组 
void update(int x) {
	for (; x > 0; x -= (x & -x)) {
		++c[x];
	}
}

ll query(int x) {
	ll res = 0;
	for (; x < maxn; x += (x & -x)) {
		res += c[x];
	}
	return res;
}

void solve() {
	scanf("%d", &n);
	a[0] = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
		a[i] += a[i-1];
	}
//	print_a("pre sum");
	for (int i = 1; i <= n; ++i) {
		if (a[i] < 0 || a[i] > a[n]) {
			printf("-1\n");
			return;
		}
	}
	
	vector<ll> ve(n);
	for (int i = 1; i <= n; ++i) {
		ve.push_back(a[i]);
	}
	sort(all(ve));
	ve.resize(unique(all(ve)) - ve.begin());
	
	ll res = 0;
	for (int i = 1; i < n; ++i) {
		int pos = upper_bound(all(ve), a[i]) - ve.begin();
		res += query(pos + 1);
		update(pos);
	}
	printf("%lld\n", res);
}

int main() {
	int t;
//	scanf("%d", &t);
	t = 1; 
	while (t--) {
		solve();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72