题目
有 (X+Y+Z) 个三元组 ((x[i],y[i],z[i]))，请你从每个三元组中挑数，并满足以下条件：
1、每个三元组中可以且仅可以选择一个数（即 (x[i],y[i],z[i]) 中的一个）
2、选择 (x[i]) 的三元组个数恰好为 (X)
3、选择 (y[i]) 的三元组个数恰好为 (Y)
4、选择 (z[i]) 的三元组个数恰好为 (Z) 问选出的数的和最大是多少
问选出的数的和最大是多少
数据规模
对于10%的数据满足，(1<=X+Y+Z<=15)
对于30%的数据满足，(1<=X+Y+Z<=100)
对于另外10%的数据满足，(X=0)
对于另外20%的数据满足，所有三元组中的 (x[i]=0)
对于另外20%的数据满足，(1<=X+Y+Z<=100000)
对于100%的数据满足，(1<=X+Y+Z<=500000，0<=x[i],y[i],z[i]<=500000)
分析
这题真妙哉！！
首先考虑 (X = 0) 时的贪心
显然先强制选所有 (y[i])
然后按 (z_i - y_i) 从大到小排序，选前 (Z) 格就行了
然后考虑 (X > 0)
先强制选所有 (x[i])
按 (z_i - y_i) 从大到小排序
枚举一个分界点
在这之前（包括本身）选 (Z) 个 (z[i])，按 (z[i]-x[i]) 从大到小选
在这之后选 (Y) 个 (y[i])，按 (y[i]-x[i]) 从大到小选
这题就可做了
当然我们显然不可能一直排序
所以我们可以用数据结构维护一下
吸口氧就过了
用桶排序即可
那我们怎样统计每次的答案呢
我们考虑每次下移临界点时，(z) 的选择就多了一个 (z[i]-x[i])，(y) 的选择就少了一个 (y[i]-x[i])
且只会这样
那么我们用双指针挪动就行
但实现细节不是那么容易
特别是 (z[i]-x[i]) 或是 (y[i]-x[i]) 有多个的时候
就要特别讨论
所以我们还有顺便维护选取的数是桶一个单元中的第几个
(Code)
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 500005;
int X, Y, Z, Tz[N << 1], Ty[N << 1], Add;
struct node{int x, y, z;}a[N];
inline bool cmp(node a, node b){return (a.z - a.y) > (b.z - b.y);}
int main()
{
freopen("triple.in", "r", stdin);
freopen("triple.out", "w", stdout);
scanf("%d%d%d", &X, &Y, &Z);
LL ans = 0, sum = 0;
for(register int i = 1; i <= X + Y + Z; i++)
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z), sum += a[i].x, Add = max(Add, max(a[i].x, max(a[i].y, a[i].z)));
sort(a + 1, a + X + Y + Z + 1, cmp);
int lz, rz, sz, ly, ry, sy;
lz = ly = Add << 1, rz = ry = 0;
for(register int i = 1; i <= Z; i++)
Tz[a[i].z - a[i].x + Add]++, lz = min(lz, a[i].z - a[i].x + Add), rz = max(rz, a[i].z - a[i].x + Add), sum += a[i].z - a[i].x;
sz = 1;
for(register int i = Z + 1; i <= X + Y + Z; i++)
Ty[a[i].y - a[i].x + Add]++, ly = min(ly, a[i].y - a[i].x + Add), ry = max(ry, a[i].y - a[i].x + Add);
for(register int i = ry, s = 0; i >= ly; i--)
if (Ty[i])
{
s += Ty[i], sum += 1LL * (i - Add) * Ty[i];
if (s >= Y){ly = i, sy = Ty[i] - (s - Y), sum -= 1LL * (i - Add) * (s - Y); break;}
}
ans = sum;
for(register int i = Z + 1; i <= X + Z; i++)
{
int del = a[i].z - a[i].x + Add;
Tz[del]++;
if (del >= lz)
{
sum += (del - Add) - (lz - Add);
if (del > rz) rz = del;
if (sz == Tz[lz])
{
++lz, sz = 1;
while (lz < rz && !Tz[lz]) ++lz;
}
else ++sz;
}
del = a[i].y - a[i].x + Add;
if (del >= ly)
{
sum -= del - Add;
if (sy >= Ty[ly])
{
--ly, sy = 1;
while (ly && !Ty[ly]) --ly;
sum += ly - Add;
}
else sum += ly - Add, ++sy;
}
Ty[del]--;
ans = max(ans, sum);
}
printf("%lld
", ans);
}