ARC187A 题解

题目分析

这个操作方式很神秘啊，怎么做？但是看到 N,K,A_i 都是 50 级别，而操作次数限制在 5\times 10^5 且不需要最优，这意味着我们使用一些比较不优的做法也可以通过。

我们考虑如果 K 是 0 的话就是冒泡排序。那么我们完全可以通过类似的方式在保持其他数相对顺序不变的前提下移动一个数。如果我们把一个数移到某个位置再移回来，可以发现这样的操作具有很好的性质：经过的数都加上了 K，而这个数本身加上了若干个 K。形式化地来说，我们可以使用 2m 次操作，使得对于任意一个 m< i\le n，使得 \forall i-m\le j<i,a_j\leftarrow a_j+K，而 a_i\leftarrow a_i+mK。

这有什么帮助呢？我们分析差分序列 b_i=a_i-a_{i-1}（a_0=0），发现上述操作使得 b_{i-m}\leftarrow b_{i-m}+K,b_i\leftarrow b_i+(m-1)\times K,b_{i+1}\leftarrow b_{i+1}-m\times K。我们发现它把 b_{i+1} 这件事情非常不优，我们不妨直接强制 i=n，那么一次操作就可以在不减小其他 b 的情况下将一个 b_i 增加 K。那么我们只需要不断进行这种操作就一定可以把 b_2\sim b_{n-1} 变成非负的。对于 b_n，我们在操作过程中把它也加了一下，但当 n=2 的时候仅通过上述操作 b_n 是一定不会改变的，需要特判。其他情况，如果 b_n 还没变成非负的我们就再随便做几次操作即可。

分析操作次数，最大应该是 (\sum\limits_{i=2}^{n-1}2[b_i<0]\lceil\frac{-b_i}K\rceil(n-i))+2[b_n<0]\lceil\frac{-b_n}K\rceil\le n^2A_i。可以通过。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,k,a[55];
vector<int>ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    if(n==2)
    {
        if(a[1]<=a[2]) 
            puts("Yes\n0");
        else
        {
            if(a[2]+k<=a[1])
                puts("Yes\n1\n1");
            else
                puts("No");
        }
        return 0;
    }
    for(int i=n;i;i--)
        a[i]-=a[i-1];
    for(int i=1;i<n;i++)
        while(a[i]<0)
        {
            for(int j=n-1;j>=i;j--)
                ans.push_back(j);
            for(int j=i;j<n;j++)
                ans.push_back(j);
            a[i]+=k;
            a[n]+=(n-i-1)*k;
        }
    while(a[n]<0)
    {
        for(int j=n-1;j;j--)
            ans.push_back(j);
        for(int j=1;j<n;j++)
            ans.push_back(j);
        a[n]+=(n-2)*k;
    }
    printf("Yes\n%d\n",ans.size());
    for(int i:ans)
        printf("%d ",i);
    return 0;
}