题意

题目链接。

给定一个序列，每次操作可以把某个数 $+1$ 或 $-1$。要求把序列变成非降数列。而且要求修改后的数列只能出现修改前的数。

解析

给出一种该题题解区中都没有提到的做法：整体二分。

对于整个区间按照值域进行二分，初始值域为负极大值到正极大值，每次二分都找出 $mid$ 值的分界线，然后对于左右两个区间依次二分。由于分界线左侧的那个数取 $mid$ 一定比取 $mid+1$ 优秀，由题目要求的非降数列可以推知整体也符合该要求，因此整体二分一定是正确的。时间复杂度为 $O(n\log v)$，$v$ 为值域，足够通过本题。

详见代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
const int inf=2e9+7;
int n,a[N],b[N];
inline void solve(int L,int R,int l,int r){
    if(L>R||l>=r) return;//边界
    int mid=(l+r)>>1,sum=0;
    for(int i=L;i<=R;i++) sum+=abs(a[i]-mid-1);
    int minn=sum,p=L-1;//初值全部定为 mid+1
    for(int i=L;i<=R;i++){
        sum-=abs(a[i]-mid-1);sum+=abs(a[i]-mid);
        if(sum<minn){
            minn=sum;
            p=i;
        }//找出分界线
    }
    for(int i=L;i<=p;i++) b[i]=mid;
    for(int i=p+1;i<=R;i++) b[i]=mid+1;//尝试赋值
    solve(L,p,l,mid);solve(p+1,R,mid+1,r);//对于两个区间依次继续二分
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    solve(1,n,-inf,inf);//整体二分
    int ans=0;
    for(int i=1;i<=n;i++) ans+=abs(a[i]-b[i]);
    printf("%lld\n",ans);//统计答案
    return 0;
}