题解：P14788 [NERC 2025] Greta' s Game

· · 题解

这里给出一个 dp 做法。

首先定义 b_i 表示第 i 个人与他后面的人一共赢的次数。

显然是要二分轮数 k。判断这个 k 是否可行可以使用 dp。

定义 dp_i=[l_i,r_i] 表示对于第 i 个人，他的 b_i 的可能的取值范围。每轮 b_i 最多增加 1，所以这个区间应该在 [0,k] 的范围之内。

由于 b_i=a_i-b_{i-1} 所以当 b_{i-1}=[L,R] 时区间最小值为 \max(a_i-R,0)，最大值为 \min(a_i-L,k)。如果最小值与最大值构成的区间不存在交集那这个 k 就不行了。

为了处理环我们直接将这个序列复制一遍就好了，还顺便省去了奇偶性讨论的麻烦。

初始区间就是 [0,k]。

由于每轮最多产生 n-1 次贡献，所以 k_{\min}=\lceil\frac{\sum{b}}{n-1}\rceil。

:::success[Code]

#include<bits/stdc++.h>
#define int long long
#define For(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
constexpr int N=5e5+5,MOD=998244353;
int t,n,a[N],aaa;
bool check(int k){
    int l=0,r=k;
    For(i,1,2*n){
        int nl=max(0ll,a[(i-1)%n+1]-r),nr=min(k,a[(i-1)%n+1]-l);
        if(nl>nr)
            return 0;
        l=nl,r=nr;
    }
    return 1;
}
void solve(){
    cin>>n;
    int sum=0,mx=0;
    For(i,1,n){
        cin>>a[i];
        sum+=a[i];
        mx=max(mx,a[i]);
    }
    int l=(sum/2+n-2)/(n-1),r=mx,ans=mx;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    cin>>t;
    while(t--)
        solve();
    return 0;
}

:::