arc187_a

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$ 。

CPP

//赛时代码可能写的有些冗余，请见谅
#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;
}

文章操作

A-Add and Swap

题意简述

Solution

相关推荐

评论

arc187_a