题解：P16993 [NWERC 2018] 倒霉下注 / Jinxed Betting

· · 题解

思路

显然最劣情况是 Julia 每场比赛都不加分，为了使它尽快被超越，所以其他人一定是能加分就加分。

以下将分数为最大值的人称为聪明人，其余人为普通人。

因为 Julia 不加分，所以肯定有一半的聪明人要和 Julia 选一样的队伍，也就是说只有另一半的聪明人可以加分。

但是普通人选择不受影响，所以他们可以加分。

假设当前有 x 个聪明人，分数均为 y，因为每次只有一半的聪明人可以加分，则聪明人在 \log_2 x 场比赛之后只剩一个了，这个人的分数是 y+\log_2 x。其他的原来的聪明人，一定是有一场比赛和 Julia 选了一样的队伍，变成了普通人，且只有那场比赛没加分，所以分数为 y+\log_2 x-1。那再一轮之后，唯一的聪明人也加不了分了，于是那些堕落的聪明人又可以借此机会变聪明了，称这是一个周期。

讲了一大堆，有什么用呢？考虑先把 p 降序排序，看当前分数最大的普通人需要几场比赛可以变成聪明人，更新聪明人的数量和进行的比赛数量即可。如果他还没来得及变成聪明人，聪明人们就超过了 Julia，那直接计算聪明人要几场比赛超过 Julia 即可。

代码

#include<bits/stdc++.h>
#define int long long
#define For(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define Fro(i,j,k) for(int i=(int)j;i>=(int)k;i--)
#define Forr(i,j,k,l) for(int i=(int)j;i<=(int)k;i+=l)
#define Fror(i,j,k,l) for(int i=(int)j;i>=(int)k;i-=l)
#define debug1 cout<<"akioi\n";
#define debug2 For(i,1,n) cout<<a[i]<<" ";
#define pb push_back
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+10,mod=1e9+7,inf=1e18;
int n,M,cnt[N],len,sum,tot,p[N],a[N];
int calc(int x){//二进制下位数
    int cnt=0;
    while(x) cnt++,x>>=1;
    return cnt;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    For(i,1,n) cin>>p[i];
    sort(p+2,p+n+1,greater<>());
    a[++len]=p[1],cnt[len]=1;
    For(i,2,n){
        if(i==2||p[i]!=p[i-1]) a[++len]=p[i],cnt[len]=1;//将相同分数的人变成一个人
        else cnt[len]++;
    }
    if(a[2]==a[1]&&cnt[2]>1) return cout<<0,0;
    M=a[2],tot=cnt[2];
    For(i,3,len){
        int c=M-a[i]-sum;//距离最大值还有几分
        int z=calc(tot)-1;//一个周期内，聪明人加的分数
        if(M+z*c>a[1]) break;
        sum+=(z+1)*c,M+=z*c,tot+=cnt[i];//更新比赛数，最大值和最大值数量
    }
    int z=calc(tot)-1;
    a[1]++;
    if((a[1]-M)%z) cout<<sum+(a[1]-M)/z*(z+1)+(a[1]-M)%z-1;
    else cout<<sum+(a[1]-M)/z*(z+1)+(a[1]-M)%z-2;
    return 0;
}