新年快乐啊
又是碌碌无为的一年啊
懵逼的 题目
BZOJ
扯淡的 题解
一开始老是往转移上面想, 比如说我
一次加一个偶数或者加两个奇数云云...后来发现似乎如果加奇数偶数的结果是一样的就GG了...
后来抄CA爷爷的题解 发现非常的厉害: 把所有的数从大到小排序,
记录每个位置的[这个位置之前的最小的偶数与这个位置之后的最大的奇数的差],
和[这个位置之前的最小的奇数与这个位置之后最大的偶数的差],
然后做前缀和
对于每一个位置, 如果这个位置的前缀和是奇数, 那很好, 直接跳过;
否则我们就要考虑花尽量少的代价来把这个前缀和改成奇数,
就用到我们预处理的东西, 挑一个小的然后减去就可以了
沙茶的 代码
这样写起来清新多了
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
#define MAXN (1000000 + 5)
#define INF (100000000000000ll + 5)
using namespace std;
int n;
LL a[MAXN], premin[2][MAXN], nexmax[2][MAXN], ans[MAXN];
bool cmp(int x, int y) { return x > y; }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
sort(a + 1, a + n + 1, cmp);
memset(premin, 0x7f, sizeof(premin));
for (int i = 1; i <= n; i++) {
premin[a[i] & 1][i] = min(premin[a[i] & 1][i - 1], a[i]);
premin[(a[i] & 1) ^ 1][i] = premin[(a[i] & 1) ^ 1][i - 1];
}
for (int i = n; i >= 1; i--) {
nexmax[a[i] & 1][i] = max(nexmax[a[i] & 1][i + 1], a[i]);
nexmax[(a[i] & 1) ^ 1][i] = nexmax[(a[i] & 1) ^ 1][i + 1];
}
for (int i = 1; i <= n; i++) a[i] += a[i - 1];
for (int i = 1; i <= n; i++)
if (a[i] & 1)
ans[i] = a[i];
else {
LL ans0, ans1;
ans0 = ans1 = INF;
if (nexmax[0][i + 1] && premin[1][i] < INF)
ans0 = premin[1][i] - nexmax[0][i + 1];
if (nexmax[1][i + 1] && premin[0][i] < INF)
ans1 = premin[0][i] - nexmax[1][i + 1];
if (ans1 >= INF && ans1 >= INF)
ans[i] = -1;
else
ans[i] = a[i] - min(ans0, ans1);
}
int q;
scanf("%d", &q);
for (int i = 1, srx; i <= q; i++)
scanf("%d", &srx), printf("%lld\n", ans[srx]);
return 0;
}
|
By 准备退役旅游的 Cansult