AT-AGC018-C 题解

allenchoi · 2024-12-16 21:27:13 · 题解

科技：

wqs 二分（板子）

思路：

首先，O(n^3) 很好做：
设二维背包 f_{i,j}，表示金币取 i 个，银币取 j 个，则有：

然后，我们不难证明 (i,f_{i,j}) 和 (j,f_{i,j}) 分别构成两个凸包：
考虑归纳。初始时，只有 f_{0,0}=0，其余可以视为负无穷，因此满足凸性。再观察转移式本质上就是将三个凸包平移后再取 \max ，显然做完这些操作后我们得到的还是凸包。
因此，我们可以先用 wqs 二分把问题从三维降至二维，变成只限制一种币取的个数。我们不妨限制银币恰好取 y 个，那么，每个人的贡献就变成了 B_i 或 \max(A_i,C_i)，并且要有恰好 y 个人选 B_i。
这个问题简单贪心即可：我们可以把所有人按 B_i-max(A_i,C_i) 排序，前 y 大的人选 B_i，后面的人都选 max(A_i,C_i)。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 5;
int n,x,y,z,cnt,a[N],b[N],c[N];
struct Node{int w1,w2,t;} p[N];
bool cmp(Node x,Node y)
{
    if(x.w2 - x.w1 != y.w2 - y.w1) return x.w2 - x.w1 > y.w2 - y.w1;
    return x.t < y.t;
}
ll check(int k)
{
    ll ret = 0;
    cnt = 0;
    for(int i = 1;i <= n;i++)
    {
        if(a[i] - k >= c[i]) p[i].w1 = a[i] - k,p[i].t = 1;
        else p[i].w1 = c[i],p[i].t = 0;
        p[i].w2 = b[i];
    }
    sort(p + 1,p + n + 1,cmp);
    for(int i = 1;i <= y;i++) ret += p[i].w2;
    for(int i = y + 1;i <= n;i++) ret += p[i].w1,cnt += p[i].t;
    return ret;
}
int main()
{
    scanf("%d%d%d",&x,&y,&z);
    n = x + y + z;
    for(int i = 1;i <= n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
    int l = -1e9,r = 1e9,mid;
    while(r - l > 1)
    {
        mid = ((l + r) >> 1);
        check(mid);
        if(cnt >= x) l = mid;
        else r = mid;
    }
    printf("%lld\n",check(l) + 1LL * l * x);
    return 0;
}