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$，可以考虑建立网络流模型处理：

• 源点 $S$ 向 $B_j$ 连一条边权为 $b_j$ 的边（注意这里的 $b_j$ 要去掉第 $i$ 个人拿走的卡牌 $j$ ），用于控制每种卡牌的总量。
• 然后 $B_j$ 向 $A_i$ 连一条边权为 $k-a_{i,j}$ 的边（不包括枚举到的这个人），用于控制最大的得分。
• 所有 $A_i$ 向汇点 $T$ 连一条边权为 $up_i$ 的边，用于控制每个人最终的总卡牌数。

显然答案有解当且仅当所有 $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=4\times 10^6$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e4+5,MAXK=4e6+5;
int a[MAXN][4],b[4],g[16][MAXN],up[MAXN],pc[16],mx[MAXN],cnt[16][MAXK];
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]
			sum[s][0]-=g[s][i],++cnt[s][0];
			sum[s][x]+=g[s][i],--cnt[s][x];
			sum[s][x]+=up[i];
		}
		for(int i=1;i<=K;++i) sum[s][i]+=sum[s][i-1],cnt[s][i]+=cnt[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) {
					ll cut=sum[s][k]+1ll*cnt[s][k]*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;
}