Description
有 $(X+Y+Z)$ 个三元组 $(x_i, y_i, z_i)$，请你从每个三元组中挑数，并满足每个三元组中可以且仅可以选择一个数，且选择 $x_i$ 的三元组个数恰好为 $X$、选择 $y_i$ 的三元组个数恰好为 $Y$、选择 $z_i$ 的三元组个数恰好为 $Z$。
问选出的数的和最大是多少。
Solution
考虑一下如果 $X = 0$ 该怎么做。
那么显然如果 $(y_i - z_i)$ 越大，将当前选的一个 $z_i$ 换为 $y_i$ 就更优。
然后取 $(y_i - z_i)$ 前 $Y$ 大的 $Y$ 个三元组的 $y_i$，然后其余的取 $z_i$ 即可。
现在考虑一下加入了 $X$ 以后怎么做。
显然如果 $(y_i - x_i)$ 越大，将当前选的一个 $x_i$ 换为 $y_i$ 就更优。
同理，如果 $(z_i - x_i)$ 越大，将当前选的一个 $x_i$ 换为 $z_i$ 就更优。
考虑先把全部的 $x_i$ 选了，然后再把选的 $Y$ 个 $x_i$ 换成 $y_i$，$Z$ 个 $x_i$ 换成 $z_i$ 即可。
然后考虑一下，如果要换的话，如果 $(z_i - y_i)$ 越大，那么换成 $z_i$ 比换成 $y_i$ 要优。
于是我们考虑先把这 $N = (X + Y + Z)$ 个三元组按照 $(z_i - y_i)$ 来排序。
由于有 $x_i$ 的干扰，我们不能够直接把前 $Z$ 个换成 $z_i$，把第 $(Z + 1)$ 到第 $(Z + Y)$ 个换成 $y_i$。
于是我们考虑枚举一个分界点，在分界点及之前的，我们可以把 $x_i$ 换成 $z_i$，在分界点之后的，我们可以把 $x_i$ 换成 $y_i$。
那如果要换的话，肯定是把 $(z_i - x_i)$ 前 $Z$ 大的 $Z$ 个三元组中选的 $x_i$ 给换成 $z_i$。
这个你可以用数据结构来维护，但是由于 $x_i, y_i, z_i$ 的值域都很小，我们可以用一个桶来维护当前的第 $Z$ 小值。
由于当分界点一直向后移的时候，存储 $(z_i - x_i)$ 的这个桶是不断加数的，比较好维护。
但 $(y_i - x_i)$ 的这个桶是不断减数的，不太好维护。
于是我们考虑把分界点一直往后挪，求出在任一分界点下，分界点及之前的这一部分的答案。
然后再把分界点一直往前挪，求出在任一分界点下，分界点之后的这一部分的答案，再与之前得到的分界点及之前的这一部分的答案相加，再取个最大值即可。
Code
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
| #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define add 500010
#define maxN 1000010
using namespace std;
struct Triplet{ long long x, y, z; } a[maxN];
long long bucket[maxN], cu[maxN];
long long min (long long x, long long y)
{
return x < y ? x : y;
}
bool cmp (Triplet A, Triplet B)
{
return A.z - A.y > B.z - B.y;
}
int main ()
{
long long Ans = 0, X = 0, Y = 0, Z = 0;
scanf("%lld %lld %lld", &X, &Y, &Z);
const long long N = X + Y + Z;
for(long long i = 1;i <= N; i++)
{
scanf("%lld %lld %lld", &a[i].x, &a[i].y, &a[i].z);
Ans += a[i].x;
}
sort(a + 1, a + N + 1, cmp);
long long nowMin = 10000000000000000LL, j = 0;
for(long long i = 1;i <= Z; i++)
{
long long x = a[i].x, z = a[i].z;
bucket[z - x + add]++;
nowMin = min(nowMin, z - x + add);
Ans += z - x;
}
cu[Z] = Ans;
const long long maxI = N - Y;
for(long long i = Z + 1;i <= maxI; i++)
{
long long x = a[i].x, z = a[i].z;
long long now = z - x + add;
if(now < nowMin)
{
cu[i] = Ans;
}
else
{
Ans -= nowMin, j++;
bucket[now]++;
if(j >= bucket[nowMin])
{
j = 0, nowMin++;
while(!bucket[nowMin])
{
nowMin++;
}
}
Ans += now;
cu[i] = Ans;
}
}
memset(bucket, 0, sizeof(bucket));
const long long minI = N - Y + 1;
nowMin = 10000000000000000LL, Ans = 0;
for(long long i = N;i >= minI; i--)
{
Ans += a[i].y - a[i].x;
long long x = a[i].x, y = a[i].y;
bucket[y - x + add]++;
nowMin = min(nowMin, y - x + add);
}
long long Res = Ans + cu[Z];
for(long long i = N - Y;i > Z; i--)
{
long long x = a[i].x, y = a[i].y;
long long now = y - x + add;
if(now < nowMin)
{
Res = max(Res, Ans + cu[i - 1]);
}
else
{
Ans -= nowMin, j++;
bucket[now]++;
if(j >= bucket[nowMin])
{
j = 0, nowMin++;
while(!bucket[nowMin])
{
nowMin++;
}
}
Ans += now;
Res = max(Res, Ans + cu[i - 1]);
}
}
printf("%lld", Res);
return 0;
}
|