题解：P14665 [KenOI 2025] 序列题

· · 题解

建议评级：黄 + / 绿。

思路

首先这个减操作可以看成对其他的数都 +1。

也就是如果把原序列看成一个环，所有的操作都可以看成区间 +1。

然后，如果对序列最大值做 +1 操作，肯定是不优的。

所以这样序列最大值就固定了。

因为极差等于最大值减最小值，最大值一定了，当最小值最大的时候，答案最优。

最小值最大，考虑二分最小值。

设二分出来的最小值为 x，我们可以知道每一个位置至少要进行的操作 l_i 与至多进行的操作数 r_i。

现在我们要求当前情况下最少进行的操作数。

因为是一个环，先破环为链，然后枚举左端点。

设 f_i 为 i 前边有多少个区间可以延申到 i 后边。

如果 l_i>f_{i-1}，那么就需要额外的 l_i-f_{i-1} 次操作，此时，f_i=l_i

否则，直接让 i-1 位置的 f_{i-1} 个区间延申过来即可，此时，f_i=f{i-1}。

但是，在这种情况下，可能会出现 f_i>r_i 的情况，这时，我们不得不舍弃一些区间，所以 f_i=r_i。

时间复杂度为 O(n^2 \log n)，可以通过。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define p_q priority_queue
#define pb push_back
#define mk make_pair
#define pii pair<int,int> 
#define ve vector
#define endl '\n'
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
namespace cute_fzj_kuai_ruarua{
    int n,m,mx=0,mn=50000;
    int a[10005],l[10005],r[10005];
    bool check(int x){
        for(int i=1;i<=n+n;i++){
            l[i]=max(0,x-a[i]);
            r[i]=mx-a[i];
        }
        for(int i=1;i<=n;i++){
            int cnt=l[i];
            int now=l[i];
            for(int j=i+1;j<=i+n-1;j++){
                if(l[j]>now){
                    cnt+=l[j]-now;
                    now=l[j];
                }
                if(now>r[j]) now=r[j];
            }
            if(cnt<=m) return 1;
        }
        return 0;
    }
    void main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) mx=max(mx,a[i]);
        for(int i=1;i<=n;i++) mn=min(mn,a[i]);
        for(int i=1;i<=n;i++){
            a[i+n]=a[i];
        }
        int l=mn,r=mx,ans=mn;
//      check(5);
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        cout<<mx-ans;
    }
}
using namespace cute_fzj_kuai_ruarua;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cute_fzj_kuai_ruarua::main();
    return 0;
}