题解：P13239 「2.48sOI R1」化妆品
最开始想着使用两个不同结构体重载排序的 deque 进行维护，然后使用二分法定位进行删除，但是发现删除仍然是 的，不可行。本蒟蒻不会写平衡树，但是会打 tag。发现如果用 used 数组进行标记每一份是否被使用，然后在从 deque 首尾取出数据时判断没有被使用过的，那么总共添加的时间复杂度应为 的，完全可以承受。最终时间复杂度为 ，瓶颈在于排序。
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
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
struct itemFas {
int f, b, ind;
bool operator < (const itemFas another) const {
return f < another.f;
}
};
struct itemBea {
int f, b, ind;
bool operator < (const itemBea another) const {
return b < another.b;
}
};
int n, m, q;
vector<bool> used;
deque<itemBea> bea;
deque<itemFas> fas;
LL f1, b1, f2, b2;
inline int read() {
int x = 0;
char ch = getchar();
while (!isdigit(ch))
ch = getchar();
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x;
}
int main() {
n = read();
m = n << 1;
used.resize(m);
bea.resize(m);
fas.resize(m);
for (int i = 0; i < m; ++i)
fas[i].f = bea[i].f = read();
for (int i = 0; i < m; ++i)
fas[i].b = bea[i].b = read();
for (int i = 0; i < m; ++i)
fas[i].ind = bea[i].ind = i;
sort(bea.begin(), bea.end());
sort(fas.begin(), fas.end());
while (n--) {
int opt = read();
if (opt == 1) {
while (!fas.empty() && used[fas.back().ind])
fas.pop_back();
f1 += fas.back().f;
b1 += fas.back().b;
used[fas.back().ind] = true;
fas.pop_back();
while (!fas.empty() && used[fas.front().ind])
fas.pop_front();
f2 += fas.front().f;
b2 += fas.front().b;
used[fas.front().ind] = true;
fas.pop_front();
} else {
while (!bea.empty() && used[bea.back().ind])
bea.pop_back();
f1 += bea.back().f;
b1 += bea.back().b;
used[bea.back().ind] = true;
bea.pop_back();
while (!bea.empty() && used[bea.front().ind])
bea.pop_front();
f2 += bea.front().f;
b2 += bea.front().b;
used[bea.front().ind] = true;
bea.pop_front();
}
}
cout << f1 << ' ' << b1 << '\n' << f2 << ' ' << b2;
return 0;
}
|
