题解：P8364 [COI2009] IZBORI

· · 题解

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

记 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
*/