自动搬运

查看原文

来自洛谷，原作者为

	_Cheems 无人扶我青云志，我自己也上不去。他们都笑话我，偏偏我也最好笑

搬运于2025-08-24 22:38:26，当前版本为作者最后更新于2024-12-24 14:09:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

初看此题，一头雾水，思绪混乱，不可做啊！故打算写一篇题解造福后人。

记 $Q_{i,j}$ 表示党派 $i$ 已经获得 $j$ 个席位时的分数。

求最大值直接把所有票送给它，然后模拟即可。

求最小值，貌似难以下手，因为难以刻画每次取最大值这一过程。不妨多确定一些信息，枚举当前 $x$ 党派最终获得 $\le p$ 个席位。显然是有单调性的，可以二分。

问题转化为：能否为其它党派分配票，满足 $x$ 党派获得席位 $\le p$，且其它党派获得的席位总和 $\ge m-mid$。

假如已经确定其它党派获得了多少票，如何求出其席位总和？由于会互相影响，还是不好搞。不妨从简单情况入手，假如只有 $1$ 个其它党派 $y$，那么它获得的席位 $p$ 满足 $Q_{y,p-1} \ge Q_{x,mid}$，否则它必然有一个席位会被 $x$ 抢走，导致 $x$ 获得 $>mid$ 个席位。

然后你发现很美妙的一点是：并不关心其它党派之间取得席位的顺序，因为我们只关心其他党派总共可以取得多少个席位。也就是说，只需按照前文的方式，分别计算每个党派取得的席位再加起来即可。

直接背包即可。现在有了个基于票数的 dp，能否优化？一个经典思想是换维，可以设 $f_{i,j}$ 表示考虑前 $i$ 个党派，让它们共取得 $\ge j$ 个席位至少要花费多少票。转移的话可以解不等式得出让 $i$ 党派获得至少 $j$ 个席位最少多少票。

还是会炸。但你注意到只有票数不小于总票数的 $\frac 1{20}$ 的党派才会获得席位，所以只看 $20$ 个党派即可。显然要尽量把票给基础票数较大的党派，于是就能过了。复杂度 $O(nm^2\log m)$，带常数 $20$。

注意一个细节：假如 $x$ 本身就小于总票数的 $\frac 1{20}$ 那么返回 $0$ 即可。

不要有畏难心理，一些看起来完全不可做的题，要尝试寻找问题性质。

代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2e2 + 5;
int cnt, lim, n, m, na, fwmx, ans[N], f[N], g[N], inf;
struct node{int a, id, s;} p[N], a[N];

inline bool cmp(node A, node B) {return A.a == B.a ? A.id < B.id : A.a > B.a;}
inline int calcmax(int pos){
	for(int i = 1; i <= n; ++i){
		a[i] = p[i];
		if(i == pos) a[pos].a += cnt;
		if(a[i].a * 20 < lim) a[i].id = -1;
	}
	for(int step = 1; step <= m; ++step){
		int mx = 0;
		for(int j = 1; j <= n; ++j){
			if(a[j].id == -1) continue;
			if(!mx || a[j].a * (a[mx].s + 1) > a[mx].a * (a[j].s + 1)) mx = j;
		}
		++a[mx].s;
	}
	return a[pos].s;
}
inline int chk(int pos, int mid){
	memset(f, 0x3f, sizeof f);
	inf = f[0], f[0] = 0;
	for(int i = 1; i <= min(20ll, n); ++i){
		if(i == pos) continue;
		for(int j = 0; j <= m; ++j) g[j] = f[j], f[j] = inf;
		for(int j = 0; j <= m; ++j)
			for(int k = 0; k <= j; ++k){
				int r;
				if(!k) r = 0;
				else{
					/*
					(a + r) >= lim / 20
					i < pos: (a + r) / k >= pos.a / (mid + 1)
					i > pos: (a + r) / k > pos.a / (mid + 1)
					*/ 
					r = max(0ll, (lim + 19) / 20 - p[i].a);
					if(p[i].id < p[pos].id) r = max(r, (k * p[pos].a + mid) / (mid + 1) - p[i].a); 
					else r = max(r, (k * p[pos].a) / (mid + 1) - p[i].a + 1);
				} 
				f[j] = min(f[j], g[j - k] + r); 
			}
	}
	return f[m - mid] <= cnt;
}
inline int calcmin(int pos){ 
	if(p[pos].a * 20 < lim) return 0; //pay attention to this
	int L = -1, R = m, mid;
	while(L + 1 < R){
		mid = (L + R) >> 1;
		if(chk(pos, mid)) R = mid;
		else L = mid;
	} 
	return R;
}
signed main(){
	cin >> cnt >> n >> m;
	lim = cnt;
	for(int i = 1; i <= n; ++i) scanf("%lld", &p[i].a), p[i].id = i, cnt -= p[i].a;
	for(int i = 1; i <= n; ++i) printf("%lld ", calcmax(i));
	putchar('\n');
	sort(p + 1, p + 1 + n, cmp);
	for(int i = 1; i <= n; ++i) ans[p[i].id] = calcmin(i);
	for(int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
	return 0;
}
/*
1000 14 50
9 54 71 16 88 150 148 29 34 47 39 44 30 57
*/