http://codeforces.com/contest/1398
E. Two Types of Spells
题意：两种咒语：fire可以造成 di 伤害，lightning可以造成 di 伤害并且使下一个咒语伤害翻倍。初始咒语集合为空，n 次，每次向集合中添加或删除一个fire或lightning，问每次修改后用集合中咒语最多造成的伤害。
模拟
策略还是比较直接的：假设集合中有 c1 个lightning，则把前 c1 大个咒语翻倍。但是要注意如果前 c1 个包含了所有lightning，则无法全部翻倍，必须放弃一个最小的lightning，再另选一个。
维护两个set，第一个维护前c1大的咒语，第二个维护剩下的。
每次操作后需要更新这两个set，此时先不考虑“lightning不能全翻倍”这一限制，在取答案时再考虑。就类似维护堆，如果插入一个数，判断如果这个数大于第一个set中最小的，则它会代替最小的，所以要把这个数插入第一个set；否则插入第二个。再根据新的c1值，删除或增加set。
要注意并不是直接插到第二个set里就好了，必须判断能否插入第一个set，否则会使得它被忽略。经常手写堆的应该就不会犯这种错了。
再考虑取答案，还要再维护一个所有lightning咒语的set，判断如果最小的lightning都在第一个set里，那么所有lightning必定都在第一个set里了，这就是我们的限制，此时需要从答案中扣去最小的lightning，加上第二个set中的最大值。
还要注意两个set里维护的是当前所有可用的咒语，在添加删除或从一个set移到另一个里时要记得更新。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1e9 + 7;
int n;
int c1;
set<int>once, twice, lig;
ll sum, sum2;
void cg() {
while ((int)twice.size() > c1) {
sum2 -= *twice.begin();
once.insert(*twice.begin());
twice.erase(twice.begin());
}
while ((int)twice.size() < c1) {
sum2 += *once.rbegin();
twice.insert(*once.rbegin());
once.erase(*once.rbegin());
}
}
void ins(int d) {
sum += d;
if (twice.empty() || d < *twice.begin())once.insert(d);
else twice.insert(d), sum2 += d;
cg();
}
void del(int d) {
sum -= d;
if (twice.count(d)) {
sum2 -= d;
twice.erase(d);
}
else {
once.erase(d);
}
cg();
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int tp, d;
scanf("%d%d", &tp, &d);
if (tp == 0) {
if (d > 0) {
ins(d);
}
else {
d = -d;
del(d);
}
}
else {
if (d > 0) {
c1++;
ins(d);
lig.insert(d);
}
else {
d = -d;
c1--;
del(d);
lig.erase(d);
}
}
ll ans = sum + sum2;
if (c1&&*lig.begin() >= *twice.begin()) {
ans -= *lig.begin();
if (!once.empty())ans += *once.rbegin();
}
printf("%lld\n", ans);
}
return 0;
}
|
