题解：CF2031B Penchick and Satay Sticks

Jerrycyx · 2024-11-17 12:17:07 · 题解

从反面思考一下，一个有序序列里任意一个元素最多被交换一次，所以要让一个无序序列通过这种方式变得有序，每个元素也只能被交换最多一次。尝试交换所有可以交换的逆序对，最后判断是否有序即可。

const int N=2e5+5;
int n,a[N];

int main()
{
    int T; read(T);
    while(T--)
    {
        read(n);
        for(int i=1;i<=n;i++)
            read(a[i]);
        for(int i=2;i<=n;i++)
            if(a[i-1]-a[i]==1) swap(a[i-1],a[i]);
        puts(is_sorted(a+1,a+n+1)?"YES":"NO");
    }
    return 0;
}