非常棒的思维题！！
半天都做不起，我咋这么菜……
一、
递增序列将每位-i就变成了非递减序列
于是我们将(a_i-i)，最后将答案(+i)变成了求非递减序列
二、
考虑初中数学题
求(|x-a|+|x-b|)的最小值，显然(xin[a,b](a<=b))时最小
同理对于一个序列，我们只要找到其中位数即是最小答案（偶数位的中位数为中间两个数的平均数，但中间两个数区间内的数都可以，我们默认选较后面那位）
三、
尝试找到一种区间的划分，使得每一段区间的中位数呈非递减序列（这样就找到一组最优解了）
每次进一个新元素的时候，自己成一个区间，如果比末尾的区间的中位数就合并两区间，重新找中位数
四、
需要支持插入+合并动态维护区间中位数的数据结构，用左偏树（可并堆）大根堆实现，每次合并后，若堆的大小太大就合并左右儿子（弹掉最大值），最后每个堆的根节点就是中位数
我咋这么菜……
只可意会不可言传！贪心乱搞
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
const int N=1e6+4;
int n,m,dis[N],a[N],ed[N],rt[N],sz[N],ch[N][2];
#define lc ch[p][0]
#define rc ch[p][1]
int merge(int p,int x){//大根堆
if(!p||!x)return p|x;
if(a[p]<a[x])p^=x^=p^=x;
rc=merge(rc,x);
if(dis[lc]<dis[rc])lc^=rc^=lc^=rc;
dis[p]=dis[rc]+1;
sz[p]=sz[lc]+sz[rc]+1;
return p;
}
inline void adjust(){
static int p;
while((ed[m]-ed[m-1]+1>>1)<sz[p=rt[m]])
rt[m]=merge(lc,rc);
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read()-i;
m++;ed[m]=rt[m]=i;sz[i]=1;
while(a[rt[m-1]]>a[rt[m]]){
rt[m-1]=merge(rt[m-1],rt[m]);
ed[m-1]=ed[m];
m--;
adjust();
}
}
long long ans=0;
for(int i=1,j=1;i<=m;i++)
for(;j<=ed[i];j++)
ans+=abs(a[j]-a[rt[i]]);
cout<<ans<<"
";
for(int i=1,j=1;i<=m;i++)
for(;j<=ed[i];j++)
cout<<a[rt[i]]+j<<" ";
return (0-0);
}
题解代码
#include <bits/stdc++.h>
using namespace std;
inline int read() {
static int ch, x;
while (isspace(ch = getchar())) {}
x = ch ^ 48;
while (isdigit(ch = getchar())) x = (((x << 2) + x) << 1) + (ch ^ 48);
return x;
}
#define MAXN 1000010
int a[MAXN], b[MAXN];
priority_queue<int> q;
int main() {
const int &n = read();
long long ans = 0;
for (int i = 1; i <= n; ++i) {
a[i] = read() - i;
q.push(a[i]);
if (q.top() > a[i]) {
q.pop();
q.push(a[i]);
}
b[i] = q.top();
}
for (int i = n; i; --i) {
ans += abs(a[i] - b[i]);
b[i - 1] = min(b[i - 1], b[i]);
}
ios::sync_with_stdio(false);
cout.tie(nullptr);
cout << ans << '
';
for (int i = 1; i <= n; ++i) {
cout << (b[i] + i) << ' ';
}
return 0;
}