CF1861F 题解

· · 题解

CF1861F 题解

Problem Link

题目大意

有 n 个人，4 种不同的卡牌，初始第 i 个人有 a_{i,j} 张第 j 种卡牌。

你是局外人，手里第 j 种卡牌有 b_j 个，你现在要把你的卡牌分给这 n 个人，使得分完之后每个人手里的卡牌总数相等，保证有解。

第 i 个人最终的分数是手里每种卡牌的数量的最大值。分数最高的那个人如果分数为 x，除了他之外分数最高的人的分数为 y，那么他会获得 x-y 的喜悦程度（显然如果存在两个分数最高的，那么他们的喜悦度都是 0），其他人会获得 0 的喜悦程度。

对于每个人，算出他最大的可能的喜悦程度。

数据范围：n\le 5\times 10^4,a_i,b_j\le 10^6。

思路分析

设 K 为最终每个人的总卡牌数，up_i=K-\sum_j a_{i,j} 表示第 i 个人距离拿满还差多少。

考虑分开处理，枚举第 i 个人手中得分来自哪种卡牌 j，显然这种牌一定尽可能取到最大值，即给 \min(b_j,up_i) 个。

剩下的就是最小化其余人的最大的得分，显然先二分一个最大值上界 k，可以考虑建立网络流模型处理：

显然答案有解当且仅当所有 A_i\to T 满流，注意不能判断 S\to B_j 满流，因为这里面还会剩下一点给第 i 个人的其他 3 种的卡牌。

考虑最大流转最小割，显然期望最大流 F^* 能算出来，那么我们只要判断是否所有割的权值都 \ge F^* 即可。

考虑枚举保留那些 S\to B_j 的边，记为 s，那么首先有 \sum_{j\not\in s} b_j 的代价。

然后考虑每个人的贡献，显然若想使 i,T 不连通，要么切掉 A_i\to T，要么切掉所有 B_j\to A_i(j\in s)，那么其贡献就是 \min(a_i,|s|\times k-\sum_{j\in s}a_{i,j})。

对于每个 s，显然可以通过差分预处理出每个 k 所对应的答案，然后就可以直接 check 了。

时间复杂度 \mathcal O(nm^22^m\log V+2^mV)，其中 n=5\times 10^4,m=4,V=6\times 10^6。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e4+5,MAXK=6e6+5;
int a[MAXN][4],b[4],g[16][MAXN],up[MAXN],pc[16],mx[MAXN],val[16][MAXN];
ll sum[16][MAXK],totup;
signed main() {
    int n,K=0,le0=0,le1=0;
    scanf("%d",&n);
    for(int i=1;i<16;++i) pc[i]=1+pc[i&(i-1)];
    for(int i=1;i<=n;++i) {
        for(int j:{0,1,2,3}) scanf("%d",&a[i][j]),K+=a[i][j];
        mx[i]=*max_element(a[i],a[i]+4);
        le1=max(le1,min(le0,mx[i])),le0=max(le0,mx[i]);
    }
    for(int i:{0,1,2,3}) scanf("%d",&b[i]),K+=b[i]; 
    K/=n;
    for(int i=1;i<=n;++i) {
        for(int j:{0,1,2,3}) up[i]+=a[i][j];
        up[i]=K-up[i],totup+=up[i];
        for(int s=1;s<16;++s) {
            for(int j=0;j<4;++j) if(s&(1<<j)) g[s][i]+=a[i][j];
        }
    }
    for(int s=1;s<16;++s) {
        for(int i=1;i<=n;++i) {
            int x=(up[i]+g[s][i])/pc[s]+1; //max k: k|s|-g[i][s]<=up[i]
            val[s][i]=x,sum[s][0]-=g[s][i],sum[s][x]+=g[s][i]+up[i];
        }
        sort(val[s]+1,val[s]+n+1);
        for(int i=1;i<=K;++i) sum[s][i]+=sum[s][i-1];
    }
    for(int i=1;i<=n;++i) {
        int ans=0,le=(le0==mx[i])?le1:le0;
        for(int j:{0,1,2,3}) {
            int cur=min(up[i],b[j]),l=le,r=K,res=K;
            b[j]-=cur;
            function<bool(int)> check=[&](int k) {
                for(int s=0;s<16;++s) {
                    int d=n-(upper_bound(val[s]+1,val[s]+n+1,k)-val[s])+1;
                    ll cut=sum[s][k]+1ll*d*pc[s]*k;
                    cut-=min(pc[s]*k-g[s][i],up[i]);
                    for(int x:{0,1,2,3}) if(!(s&(1<<x))) cut+=b[x];
                    if(cut<totup-up[i]) return false; //mincut <= expected flow
                }
                return true;
            };
            while(l<=r) {
                int mid=(l+r)>>1;
                if(check(mid)) r=mid-1,res=mid;
                else l=mid+1;
            }
            ans=max(ans,a[i][j]+cur-res),b[j]+=cur;
        }
        printf("%d ",ans);
    }
    puts("");
    return 0;
}