题目概述

有 $n$ 个组 $V$ 张票，假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会，令 $S_i$ 表示目前 $i$ 组被钦点了几次，每次会钦点 $V_i\over{S_i+1}$ 最小的组。但是现在投票还没有结束，$V$ 和每个组目前票数已知，问每个组最多最少被钦点几次。

解题报告

第一问直接把所有票数给一个组然后模拟一下就好了……

第二问好像以前做过类似的……我们把组按照当前票数 $a_i$ 排序，可以考虑DP $f_{i,j}$ 表示前 $i$ 组总共被钦点 $j$ 次需要的最少票数（肯定尽量给比 $i$ 大的组而不会给比 $i$ 小的组），这样 $f_{i,m-x}\le V-\sum_{i=1}^{n}a_i$ 中最小的 $x$ 就是 $i$ 组的答案。

但是转移过程中会求至少需要多少票，这是只有得知了 $i$ 组最终有多少席位才能算出来的，所以我们需要先二分，然后用DP验证。

有很多细节……比如相同取编号小的……票数不足够 $5\%$ 留不下来……

示例程序

#include<cstdio>
#include<cstring> 
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=20,maxm=200;

int V,n,m,sum,a[maxm+5],b[maxm+5],ID[maxm+5],ans[maxm+5],f[maxn+5][maxm+5];

inline bool cmp(int x,int y) {return a[x]>a[y];}
inline bool check(int x,int mid){
    memset(f,63,sizeof(f));f[0][0]=0;
    for (int i=1;i<=n&&i<=20;i++){
        if (i==x) {for (int j=0;j<=m;j++) f[i][j]=f[i-1][j];continue;}
        for (int j=0;j<=m;j++)
            for (int k=0;k<=j;k++){
                int val=max((a[x]*k+mid)/(mid+1)-a[i]+(!(a[x]*k%(mid+1))&&ID[i]>ID[x]&&k),0);
                if (k&&(a[i]+val)*20<V) val+=(V-20*(a[i]+val)+19)/20;f[i][j]=min(f[i][j],f[i-1][j-k]+val);
            }
    }return f[min(n,20)][m-mid]<=V-sum;
}
inline int Solve(int x,int L=0,int R=m){
    if(a[x]*20<V) return 0;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        check(x,mid)?R=mid-1:L=mid+1;return L;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&V,&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    for (int i=1;i<=n;i++){
        a[i]+=V-sum;for (int j=1;j<=n;j++) b[j]=0;
        for (int j=1,ID=-1;j<=m;j++,b[ID]++,ID=-1)
            for (int k=1;k<=n;k++) if(a[k]*20>=V&&(ID<0||a[k]*(b[ID]+1)>a[ID]*(b[k]+1))) ID=k;
        printf("%d",b[i]);putchar(i<n?' ':'\n');a[i]-=V-sum;
    }for (int i=1;i<=n;i++) b[i]=a[i],ID[i]=i;sort(ID+1,ID+1+n,cmp);
    for (int i=1;i<=n;i++) a[i]=b[ID[i]];for (int i=1;i<=n;i++) ans[ID[i]]=Solve(i);
    for (int i=1;i<=n;i++) printf("%d",ans[i]),putchar(i<n?' ':'\n');return 0;
}