CF1585D Yet Another Sorting Problem

题目大意

给定一个\(n\)个数的数组\(a\)。

每次可以选择三个数\(a_i, a_j, a_k(1 \le i,j,k \le n)\),使得\(a_i\)到\(a_j\)原来的位置,\(a_j\)到\(a_k\)原来的位置,\(a_k\)到\(a_i\)原来的位置。(\(1 \le n, a_i \le 10^5\))

问是否可以通过这种方式使得数组变成升序有序数组 题目地址

思路

首先需要知道这么一个规律,交换一个序列中两个不同的数会使这个序列的逆序对数改变奇数个。

而题目的这种操作就像与连续进行两次操作(交换\(a_i, a_j\),然后交换\(a_j ,a_k\)),那么显然逆序数的变换是偶数个。

所以,只要原序列的逆序数是偶数,那么肯定可以做到。

当然还有一种特殊情况:

有两个相同的数,那么我们可以把这两个数作为媒介,可以等价于随意交换任意两个数,所以此时无论如何都能交换成功。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxN = 5e5 + 7;

int T, n, a[maxN], b[maxN], c[maxN];

bool cmp(int x, int y)
{
    return x < y;
}

inline void Add(int x, int k)
{
    for(; x <= n; x += x&(-x))
        c[x] += k;
}

inline int GetSum(int x)
{
    int ans = 0;
    for(; x; x -= x&(-x))
        ans += c[x];
    return ans;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        sort(a + 1, a + 1 + n, cmp);
        int cnt = 0; bool mul = false;
        for(int i = 1; i <= n; ++i)
            if(a[i] == a[i - 1]) { //判断是否有重复
                mul = true;
                break;
            }
        if(mul)
            printf("YES\n");
        else  {
            int num = 0;
            memset(c, 0, sizeof c);
            for(int i = n; i > 0; i--) {
                num += GetSum(b[i] - 1);
                Add(b[i], 1);
            }
            if(num & 1)
                printf("NO\n");
            else
                printf("YES\n");
        }
    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/12/23/CF1585D/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！