题解：P14665 [KenOI 2025] 序列题

· · 题解

题解：P14665 [KenOI 2025] 序列题

题意已经很清晰了，这里就不讲题意了。

思路

  1. 记操作后 a_i 的值为 a'_i，则每个位置的改变量 \Delta_i=a'_i-a_i。最少操作数可以写成：

    \text{ops}(\Delta)=\frac{1}{2}(|\Delta_1|+\sum_{i=2}^n|\Delta_i-\Delta_{i-1}|+|\Delta_n|)

  2. 给定目标极差 K，若存在某个整数区间 [L,L+K] 和一组 \Delta_i，使得：

    L\le a_i+\Delta_i\le L+K

    且上式中的 \text{ops}(\Delta)\le m，则极差 K 可行。

  3. 固定 K,L 时，每个 \Delta_i 必须在区间 [L-a_i,L-a_i+K] 内。这里可以使用贪心维护当前值 \text{cur}：

    • 对每个区间 [l_i,r_i]：
      • 若 \text{cur} < l_i，跳到 l_i，加代价 l_i-\text{cur}；
      • 若 若 \text{cur} > r_i，跳到 r_i，加代价 r_i-\text{cur}；
      • 否则不动。
    • 最后从 \text{cur} 跳回 0，加代价 |\text{cur}|。 总代价的一半就是所需操作数的最小值 \text{cost}(L)。

  4. 对于固定的 K，函数 \text{cost}(L) 是关于 L 的单峰函数， 因此可以三分 L，再在最后的区间内枚举求最小值。

  5. 外层二分 K，从 0 到初始极差 \text{mx} - \text{mn}。

最后时间复杂度约为二分 O(\log{n}) 三分 O(\log{n}) 枚举 O(n) 一共 O(n\log^2{n})，可以跑 n=10^5。

代码

前面是我的火车头很长 qaq

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/list_update_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#include<ext/rope>
#define Int signed
#define For(a,b,c) for(int a=b;a<=c;a++)
#define Fro(a,b,c) for(int a=b;a>=c;a--)
#define ms(a) memset(a,0,sizeof a)
#define msinf(a) memset(a,0x3f,sizeof a)
#define precision(x) fixed<<setprecision(x)
#define pii pair<int,int>
#define ls (id<<1)
#define rs (id<<1|1)
#define fi first
#define se second
#define y1 y1ovo
#define y2 y2ovo
#define j1 j1ovo
#define j2 j2ovo
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ull unsigned int
#define lll __int128
#define lld long double
#define Ceil(a,b) ceil(1.0*a/b)
#define Floor(a,b) floor(1.0*a/b)
#define stdpq std::priority_queue
#define pbpq __gnu_pbds::priority_queue
#define Fopen(in,out) freopen(in,"r",stdin);freopen(out,"w",stdout);
#define Happy return
#define Ending 0
#define LL 1
#ifdef LL
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
using namespace __gnu_pbds;using namespace __gnu_cxx;
namespace fast_IO{
#define FASTIO
#define IOSIZE 1048576
#define ONLINE_JUDGE 1
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    char ibuf[IOSIZE],obuf[IOSIZE];char *p1=ibuf,*p2=ibuf,*p3=obuf;template<typename T>inline T read() {T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch !=EOF))if(ch=='-') w=-1;if(ch==EOF) return false;while(isdigit(ch)) s=(s<<1)+(s<<3)+ch-48,ch=getchar();return s*w;}template<typename T> inline bool read(T &s) {s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch) and(ch !=EOF)) if(ch=='-') w=-1;if(ch==EOF) return false;while(isdigit(ch))s=(s<<1)+(s<<3)+ch-48,ch=getchar();return s*=w,true;}inline bool read(char &s) {while(s=getchar(),isspace(s));return true;}inline bool read(char *s) {char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x) {if(x<0) putchar('-'),x=-x;if(x>9) print(x / 10);putchar(x % 10+48);}inline void print(char x) {putchar(x);}inline void print(char *x) {while(*x) putchar(*x++);}inline void print(const char *x) {for(int i=0; x[i]; i++) putchar(x[i]);}
#ifdef _GLIBCXX_STRING
    inline bool read(std::string& s) {s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF) return false;while(!isspace(ch)) s+=ch,ch=getchar();return true;}inline void print(std::string x) {for(int i=0,n=x.size(); i<n; i++)putchar(x[i]);}
#endif
    template<typename T,typename... T1>inline int read(T& a,T1&... other) {return read(a)+read(other...);}template<typename T,typename... T1>inline void print(T a,T1... other) {print(a);print(other...);}
    struct Fast_IO {~Fast_IO() {fwrite(obuf,p3-obuf,1,stdout);}} io;template<typename T>Fast_IO&operator>>(Fast_IO &io,T &b) {return read(b),io;}template<typename T>Fast_IO&operator<<(Fast_IO &io,T b) {return print(b),io;}
#define cout io
#define cin io
#define endl '\n'
}using namespace fast_IO;
template<typename T> using Set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;template<typename T,typename TT> using Map=gp_hash_table<T,TT>;

/*------------从这里开始-------------*/

const int N=5005;
int n,m;
int a[N];
int mn=inf,mx=-inf;
int ck;
int calc(int L){
    int cost=0;
    int cur=0;
    For(i,1,n){
        int l=L-a[i];
        int r=L-a[i]+ck;
        if(cur<l)
            cost+=l-cur,cur=l;
        else if(cur>r)
            cost+=cur-r,cur=r;
    }
    cost+=abs(cur);
    return cost>>1;
}
bool check(int mid){
    ck=mid;
    int low=mn-m;
    int high=mx+m;
    if(low>high)low=high=0;
    while(high-low>10){
        int m1=(low*2+high)/3;
        int m2=(low+high*2)/3;
        int c1=calc(m1);
        int c2=calc(m2);
        if(c1<=c2) high=m2-1;
        else low=m1+1;
    }
    int best=inf;
    For(L,low,high){
        int c=calc(L);
        if(c<best)best=c;
    }
    return best<=m;
}
Int main(){
    cin>>n>>m;
    For(i,1,n)
        cin>>a[i],mx=max(mx,a[i]),mn=min(mn,a[i]);
    int l=0,r=mx-mn,ans=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))
            ans=mid,r=mid-1;
        else 
            l=mid+1;
    }
    cout<<ans;
    Happy Ending;
}