Skip to content

AGC018C - Coins

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#Statement

There are X+Y+ZX + Y + Z people, conveniently numbered 11 through X+Y+ZX + Y + Z. Person ii has AiA_i gold coins, BiB_i silver coins and CiC_i bronze coins.

Snuke is thinking of getting gold coins from XX of those people, silver coins from YY of the people and bronze coins from ZZ of the people. It is not possible to get two or more different colors of coins from a single person. On the other hand, a person will give all of his/her coins of the color specified by Snuke.

Snuke would like to maximize the total number of coins of all colors he gets. Find the maximum possible number of coins.

#Samples

Sample Input #1

1 2 1
2 4 4
3 2 1
7 6 7
5 2 3

Sample Output #1

18

Sample Explanation #1

Get silver coins from Person 11, silver coins from Person 22, bronze coins from Person 33 and gold coins from Person 44. In this case, the total number of coins will be 4+2+7+5=184 + 2 + 7 + 5 = 18. It is not possible to get 1919 or more coins, and the answer is therefore 1818.

Sample Input #2

3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2

Sample Output #2

110

Sample Input #3

6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164

Sample Output #3

3093929975

#Limits

  • 1X,Y,Z1 \leq X, Y, Z
  • X+Y+Z105X + Y + Z \leq 10^5
  • 1Ai,Bi,Ci1091 \leq A_i, B_i, C_i \leq 10^9

#题解

反悔贪心。

先钦定所有人全拿铜牌,然后再考虑拿金牌、银牌的情况。那么问题就转化为了选出 xx 人给 aicia_i - c_i 元,yy 人给 bicib_i - c_i 元。

容易想到按照 aibia_i - b_i 降序排序来确定拿金牌的选手到底是哪些。接下来维护金牌的前缀和和银牌的后缀和即可,由于数组已经以 aibia_i - b_i 为关键字排过序了,所以这样维护是正确的。

#代码

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
#include <iostream>
#include <algorithm>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, x, y, z;
long long pre[N], suf[N], sum, ans;

struct node {
int a, b, c, id;
} a[N];

std::priority_queue<int> q1, q2;

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> x >> y >> z;

n = x + y + z;

for (int i = 1; i <= n; i++) {
cin >> a[i].a >> a[i].b >> a[i].c;

sum += a[i].c; // 先钦定全选铜牌
a[i].id = i;
}

std::sort(a + 1, a + 1 + n, [](node a, node b) {
return a.a - a.b > b.a - b.b; // 按照 a - b 降序排序
});

for (int i = 1; i <= n; i++) {
q1.push(a[i].c - a[i].a); // 计算更换为铜牌的代价并插入堆中
pre[i] = pre[i - 1] + a[i].a - a[i].c;

if (q1.size() > x) { // 如果金牌数量超出要求则将最小的更改为铜牌
pre[i] += q1.top();
q1.pop();
}
}

for (int i = n; i; i--) {
q2.push(a[i].c - a[i].b); // 计算更换为铜牌的代价并插入堆中
suf[i] = suf[i + 1] + a[i].b - a[i].c;

if (q2.size() > y) { // 如果银牌数量超出要求则更改为铜牌
suf[i] += q2.top();
q2.pop();
}
}

for (int i = x; i + y <= n; i++) {
ans = std::max(ans, sum + pre[i] + suf[i + 1]);
}

cout << ans << endl;

return 0;
}

原题来自 AGC018C - Coins