首先掏出一张草稿纸,随便写几种情况,发现可以对 i 进行两次操作后可以将 a_i,a_{i+1} 都加上 k。
i |
i+1 |
a_i |
a_{i+1} |
a_{i+1}+k |
a_i |
a_i+k |
a_{i+1}+k |
于是有了这样一个思路:枚举 i\in(1,n),如果 a_i<a_{i-1},那么反复增加 a_i,a_{i+1},直到 a_i\ge a_{i-1}。
看上去很对,但是问题来了,没有办法对 n 操作,如果最后 a_{n-1}>a_n,是没有办法解决的。
继续手玩,发现对于长度为 len 的区间 [l,r] 可以通过 len 次 l,l+1,l+2,\cdots,r-2,r-1 操作对区间加 (len-1)\cdot k。
一次 l,l+1,l+2,\cdots,r-2,r-1 操作的过程。 |
l |
l+1 |
\cdots |
r |
a_l |
a_{l+1} |
\cdots |
a_r |
a_{l+1}+k |
a_l |
\cdots |
a_r |
\vdots |
\vdots |
\ddots |
\vdots |
a_{l+1}+k |
a_{l+2}+k |
\cdots |
a_1 |
|$l$|$l+1$|$\cdots$|$r$|
|:-:|:-:|:-:|:-:|
|$a_l$|$a_{l+1}$|$\cdots$|$a_r$|
|$a_{l+1}+k$|$a_{l+2}+k$|$\cdots$|$a_l$|
|$a_{l+2}+2\times k$|$a_{l+3}+2\times k$|$\cdots$|$a_{l+1}+k$|
|$\vdots$|$\vdots$|$\ddots$|$\vdots$|
|$a_{l}+(len-1)\cdot k$|$a_{l+1}+(len-1)\cdot k$|$\cdots$|$a_r+(len-1)\cdot k$|
于是我们可以枚举 $i\in(1,n)$,如果 $a_i<a_{i-1}$,那么反复增加 $a_i,a_{i+1},\cdots,a_n$,直到 $a_i\ge a_{i-1}$,这样就解决了原本 $a_{n-1}\le a_n$,但因为一些操作导致 $a_{n-1}>a_n$ 的问题,因为 $a_{n-1}$ 和 $a_n$ 总是一起增加,所以相对大小关系不变。
如果刚开始就有 $a_{n-1}>a_n$ 怎么办?
显然,如果无法让它俩有序就无解。
当 $n>2$ 时一定有解,反复对 $n-1$ 操作直到 $a_n\ge a_{n-2}$,然后对 $n-2$ 操作,这样就有 $a_n\ge a_{n-1}$。
否则只需要对 $1$ 做一次操作,如果 $a_n\ge a_{n-1}$ 则有解,否则无解。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[100];
vector<int>ans;
void add(int pos){//后缀加
int len=n-pos+1;
for(int i=1;i<=len;i++){
for(int j=pos;j<n;j++)ans.push_back(j);
}
for(int i=pos;i<=n;i++)a[i]+=k*(len-1);
}
void slv(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
if(a[n-1]>a[n]){
if(n==2){
swap(a[n],a[n-1]);//对1做一次操作
a[n-1]+=k;
if(a[n-1]<=a[n])cout<<"Yes\n1\n1";//不降则有解
else cout<<"No";//下降则无解
return;
}
while(a[n]<a[n-2]){
a[n]+=k;
a[n-1]+=k;
ans.push_back(n-1),ans.push_back(n-1);
}
swap(a[n-1],a[n-2]);
a[n-2]+=k;
ans.push_back(n-2);
}
for(int i=2;i<n;i++){
while(a[i]<a[i-1])add(i);//后缀加直到比上一个大
}
cout<<"Yes"<<endl;
cout<<ans.size()<<endl;
for(int x:ans)cout<<x<<" ";
}
signed main(){
slv();
return 0;
}
```