首先题意很明显就不说了吧www
先说一下做这道题的经历
昨天下午和 blw 一起去食堂吃饭,和他产生了一点儿冲突,于是我考了一下他 P1119 (就是那道 Floyd),他很快做出来了,于是考了我这道题,并称其为“神仙结论题”
首先我 10min 就搞出了正解,然而 blw 说我 WA 了,我就很谔谔,或许是他搞错了吧qaq
并且吐槽一句这题结论不难想啊
首先这道题序列单调递增,所以不论怎么操作最后的序列都是单调不降的。
并且,还有一个明显能够得到的结论:
若 \([a_L+1<a_{L+1}][a_{R-1}+1<a_R][\sum_{i=L+1}^{R-1}[a_i<a_{i+1}]] = 1\),那么可以让 \(a_L\) 加一,\(a_R\) 减一。
证明很简单,略。
于是,我们每次就让最右边能够产生“山体滑坡”(本题的名称,也相当于最右边能够进行操作的数)减尽量多,最左边能够进行“山体滑坡”的数加上这个数。
于是左边的数就会尽量大,右边的数就会尽量小。
再由于题意,能够得到最多只有两个相邻的项相等。
于是我们就得出了以下算法:
先算出最所有项的和,然后算出 \(a_1\),由结论得:\(a_i = a_{i-1}+1\)。
这时用最开始所有项的和减去现在所有项的和,还会剩下 \(O(n)\) 的值。
从左往右一个一个填即可。
code:
#include<cstdio>
#include<cctype>
typedef long long ll;
const int M=1e6+5;
int n;
ll sum,ans,a[M];
inline ll read(){
ll a=0;char s;
while(!isdigit(s=getchar()));
while(a=a*10+(s^48),isdigit(s=getchar()));
return a;
}
signed main(){
int i;
n=read();
for(i=1;i<=n;++i)a[i]=read(),sum+=a[i];
sum-=1ll*n*(n+1)>>1;
ans=sum/n;sum-=ans*n;
for(i=1;i<=n;++i)a[i]=ans+i;
i=1;
while(sum--)++a[i++];
for(i=1;i<=n;++i)printf("%lld ",a[i]);
}