[Gym102201E] Eat Economically

发这篇博客主要是为了记录一个极为隐蔽的错误。

写比较函数一定要保证是严格的小于号。要特别处理等于。否则在遇到堆打标记删除这种问题的时候,相同元素在堆中的顺序会影响答案。

代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 250010;

ll ans[maxn];
int L[maxn<<1], D[maxn<<1], a[maxn<<1], n;

struct C1 {
bool operator()(const int &x, const int &y) {
if (L[x] == L[y]) return x < y;
return L[x] > L[y];
}
};

struct C2 {
bool operator()(const int &x, const int &y) {
if (D[x] == D[y]) return x < y;
return D[x] > D[y];
}
};

struct C3 {
bool operator()(const int &x, const int &y) {
if (L[x]-D[x] == L[y]-D[y]) return x < y;
return L[x]-D[x] > L[y]-D[y];
}
};

struct C4 {
bool operator()(const int &x, const int &y) {
return D[x]-L[x] > D[y]-L[y];
}
};

template<typename T1, typename T2>
struct Heap {
priority_queue<T1, vector<T1>, T2> q, d;
void _c() {
while (!d.empty() && q.top() == d.top()) {
q.pop();
d.pop();
}
}
T1 getTop() {
_c();
if (!q.empty()) return q.top();
else return 0;
}
void del(T1 x) {
d.push(x);
}
void add(T1 x) {
q.push(x);
}
int size() {return int(q.size())-int(d.size());}
};

Heap<int, C3> h1;
Heap<int, C4> h2;
Heap<int, C1> h3;
Heap<int, C2> h4;
int vis[maxn<<1];

int main() {
L[0] = D[0] = 0x7fffffff;
scanf("%d", &n);
for (int i = 1; i <= 2*n; i++) scanf("%d%d", &L[i], &D[i]);
for (int i = 1; i <= 2*n; i++) h3.add(i), h4.add(i);
for (int i = 1; i <= n; i++) {
ans[i] = ans[i-1];
{
int v1 = h3.getTop(), v2 = h4.getTop(), v3 = h1.getTop();
if (!v3 || L[v1] < L[v3]-D[v3]+D[v2]) {
ans[i] += L[v1];
h2.add(v1);
h3.del(v1);
h4.del(v1);
} else {
ans[i] += L[v3]-D[v3]+D[v2];
h1.del(v3);
h2.add(v3);
h1.add(v2);
h3.del(v2);
h4.del(v2);
}
}
{
int v1 = h4.getTop(), v2 = h3.getTop(), v3 = h2.getTop();
if (!v3 || D[v1] < D[v3]-L[v3]+L[v2]) {
ans[i] += D[v1];
h1.add(v1);
h4.del(v1);
h3.del(v1);
} else {
ans[i] += D[v3]-L[v3]+L[v2];
h2.del(v3);
h1.add(v3);
h2.add(v2);
h4.del(v2);
h3.del(v2);
}
}
}
for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
return 0;
}