有 \(n\) 个人，\(4\) 种不同的卡牌，初始第 \(i\) 个人有 \(a_{i,j}\) 张第 \(j\) 种卡牌。
你是局外人，手里第 \(j\) 种卡牌有 \(b_j\) 个，你现在要把你的卡牌分给这 \(n\) 个人，使得分完之后每个人手里的卡牌总数相等，保证有解。
第 \(i\) 个人最终的分数是手里每种卡牌的数量的最大值。分数最高的那个人如果分数为 \(x\)，除了他之外分数最高的人的分数为 \(y\)，那么他会获得 \(x-y\) 的喜悦程度（如果存在两个分数最高的，那么他们的喜悦度都是 \(0\)），其他人会获得 \(0\) 的喜悦程度。
对于每个人，算出他最大的可能的喜悦程度。
\(2 \le n \le 5 \times 10^4\)，\(0 \le b_j,a_{i,j} \le 10^6\)。
设 \(M\) 为最终每个人的总卡牌数，\(c_i = M - \sum\limits_j a_{i,j}\) 表示第 \(i\) 个人需要收到多少张牌。
考虑怎么计算一个人 \(i\) 的答案，假设我们希望第 \(i\) 个人最多的卡牌为类型 \(j\)，那么通过调整可以证明，最优策略一定是尽可能将类型 \(j\) 的卡牌给 \(i\)。显然我们最多能给 \(\min(b_j,c_i)\) 个卡牌 \(j\) 给第 \(i\) 个人。这样第 \(i\) 个人每种卡牌个数的最大值就确定了，我们的目标变为让另外 \(n-1\) 个人每种卡牌个数的最大值尽可能小。考虑二分答案 \(mid\)，用网络流模型检验 \(mid\) 是否可行：
新建源点 \(S\) 和汇点 \(T\)，以及 \(x_1 \sim x_4\)，\(y_1 \sim y_n\)，连边：
- \(S \to x_i\)，容量 \(b_i\)。
- \(x_i \to y_j(j \neq i)\)，容量 \(mid - a_{j,k}\)。
- \(y_j \to T(j \neq i)\)，容量 \(c_j\)。
最后检验最大流是否为 \(\sum\limits_{i\ne j}c_j\) 即可。
然而每次检验都建一次图是没法接受的。考虑最大流最小割定理，只需要判断是否所有割的权值都 \(\geq \sum\limits_{i\ne j}c_j\) 即可。我们枚举哪些与源点相连的边没被割掉，那么割掉剩余的边的代价就是 \(\sum\limits_{i \neq j}\min(c_j,\sum\limits_{x \in S} mid - a_{j,x})\)。割掉与 \(S\) 相连的边的代价是 \(\sum\limits_{x\notin S}b_x\)。后者容易计算，前者可以对于每个 \(S\) 差分预处理出每个 \(mid\) 对应的值，就可以快速检验了。总时间复杂度 \(\mathcal{O}(n \cdot 4^2 \cdot 2^4 \log V + 2^4 \cdot V)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N = 5e4 + 5, K = 4e6 + 5;
bool Mbe;
int n, M, mx1, mx2;
int a[N][4], b[4], mx[N], c[N], val[1 << 4][N], cnt[1 << 4][K];
LL sumc, sum[1 << 4][K];
bool Med;
int main() {
// fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
ios :: sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++) cin >> a[i][j], M += a[i][j], mx[i] = max(mx[i], a[i][j]);
mx2 = max(mx2, min(mx1, mx[i]));
mx1 = max(mx1, mx[i]);
}
for (int i = 0; i < 4; i++) cin >> b[i], M += b[i];
M /= n;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++) c[i] += a[i][j];
c[i] = M - c[i], sumc += c[i];
for (int s = 0; s < 1 << 4; s++)
for (int j = 0; j < 4; j++) {
if (s & (1 << j)) val[s][i] += a[i][j];
}
}
for (int s = 1; s < 1 << 4; s++) {
for (int i = 1; i <= n; i++) {
int x = (val[s][i] + c[i]) / __builtin_popcount(s) + 1;
sum[s][0] -= val[s][i], cnt[s][0]++;
sum[s][x] += val[s][i], cnt[s][x]--;
sum[s][x] += c[i];
}
for (int i = 1; i <= M; i++) sum[s][i] += sum[s][i - 1], cnt[s][i] += cnt[s][i - 1];
}
int ans;
for (int i = 1; i <= n; i++) {
ans = 0;
int lim = mx[i] == mx1 ? mx2 : mx1;
for (int j = 0; j < 4; j++) {
int cur = min(c[i], b[j]);
int L = lim, R = M, res = M;
b[j] -= cur;
auto check = [&](int m) {
for (int s = 0; s < 1 << 4; s++) {
LL cut = sum[s][m] + 1LL * cnt[s][m] * __builtin_popcount(s) * m;
cut -= min(c[i], __builtin_popcount(s) * m - val[s][i]);
for (int k = 0; k < 4; k++) if (!(s & (1 << k))) cut += b[k];
if (cut < sumc - c[i]) return false;
}
return true;
};
while (L <= R) {
int m = L + R >> 1;
if (check(m)) R = m - 1, res = m;
else L = m + 1;
}
ans = max(ans, a[i][j] + cur - res), b[j] += cur;
}
cout << ans << " ";
}
// cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}