arc187_a

a_sad_soul · 2024-11-18 07:23:02 · 题解

A-Add and Swap

题意简述

有一个长度为 N 的序列。

现在有一个操作：

在 1~n-1 中选择一个位置 i，让 i+1 加上 K，然后交换两个数的位置。

问在 5\times 10^5 内能否让序列单调不减。如果可以，请输出操作序列。

Solution

我们先从小的地方来讨论一下：

• 当 n=2 时：若 a_1>a_2 且 a_2+K>a_1 无解。原因是重复操作某个位置偶数次，效果是让两个数同时加上偶数除以2个 K，且相对大小仍然不变。

• 当 n=3 时：由 n=2 时的结论推广一下，发现可以这样做：让后面的操作200次，前面的操作100次，最后再对中间操作1次，可以保持正确。

• 其它情况：从上述结论出发，我们可以从前往后搞一个长度为3的滑动窗口。先让后加进来的数放到窗口最前面，然后操作一次 n=3 的操作即可。注意到到后面可能有操作完的情况不合法（一个例子就是设 A_i 已经操作结束，那么可能有 a_1>a_2 的情况）。那么我们可以让第 i 次操作乘上 i 的一个偏移量即操作 200i 和 100i 次就可以避开不合法的情况了。不难证明该操作次数一定小于 5\times 10^5。

//赛时代码可能写的有些冗余，请见谅
#include<bits/stdc++.h>
using namespace std;
vector<int>ans;
int n,k;
int a[100];
void ins(int i){
    ans.push_back(i);
    a[i+1]+=k;swap(a[i],a[i+1]);
}

void PRINT(){
    if(ans.size()>5e5)exit(-1);
    puts("Yes");
    printf("%d\n",ans.size());
    for(int i:ans)printf("%d ",i);
}
bool check(int i){
    if(a[i]<a[i-1]||a[i-1]<a[i-2])return false;
    return true;
}

void change(int i){
    ins(i-1),ins(i-2);
    for(int x=1;x<=(i-2)*200;++x)ins(i-1);
    for(int x=1;x<=(i-2)*150;++x)ins(i-2);
    ins(i-1);
}

void opt(int i){
    change(i);
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    if(n==2){
        if(a[1]>a[2]&&a[2]+k>a[1]){
            puts("No");
            return 0;
        }
        puts("Yes");
        if(a[1]<=a[2])puts("0");
        else cout<<"1\n"<<"1"<<endl;
        return 0;
    }
    for(int i=3;i<=n;++i)opt(i);
    PRINT();
    return 0;
}