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

· · 题解

显然你让 a_1 变大是不优的，因为最好的情况是相当于这一轮你啥都没干。

手玩一下可以发现，一块长度为 n 且全部一样且最大的东西，经过 \lfloor\log_2n\rfloor+1 轮会增加 \lfloor\log_2n\rfloor。其它东西显然增加 \lfloor\log_2n\rfloor+1。这个东西比较显然，因为你最大的东西最多增加一半。

于是 a_2\sim a_n 从大到小排序后维护一个 p，初始 p 是最右等于 a_2 的位置。之后直接模拟操作 (a_2-a_{p+1})\times(\lfloor\log_2p\rfloor+1) 轮，这个通过上面的结论是容易做到的。如果中途达到 a_1 那答案通过这个周期显然可以直接求，否则操作这么多次之后 a_{p+1} 一定等于 a_2，向右移动 p 即可。

模拟加法操作可以维护加法标记。具体地，维护一个 ad1 表示 p 之前都是 a_2+ad1，adp 表示 p+1 之后是原本的值加上 adp。

复杂度线性。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned i32
#define inf 1e18
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf 1e9
#define infl 1e18
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
#define fileio(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N=1e6+10,mod=1e9+7;
int a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,x;
    cin>>n>>x;
    n--,x++;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    int p=1;
    while(p<n&&a[p+1]==a[p]) p++;
    int ad1=0,adp=0;//p 之前是 a_1+ad1，p 之后是 a_i+adp
    while(p<n)
    {
        int tl=a[1]+ad1-a[p+1]-adp;
        int ss=__lg(p);
        if(a[1]+ad1+tl*ss>=x)
        {
            int px=x-a[1]-ad1;
            adp+=(px-1)/ss*(ss+1);
            px-=(px-1)/ss*ss;
            adp+=px;
            cout<<adp-1;
            return 0;
        }
        ad1+=tl*ss;
        adp+=tl*(ss+1);
        p++;
        while(p<n&&a[p+1]==a[p]) p++;
    }
    int ss=__lg(n);
    int px=x-a[1]-ad1;
    adp+=(px-1)/ss*(ss+1);
    px-=(px-1)/ss*ss;
    adp+=px;
    cout<<adp-1;
    return 0;
}

:::