题解：CF1733C Parity Shuffle Sorting

zhangmuning1016 · 2025-05-12 22:15:16 · 题解

题目传送门

思路

• 观察规则可知，当 a_l+a_r 为奇数时，a_r 不等于 a_l；否则 a_l=a_r。
• 我们可以利用这个操作来逐渐调整元素的顺序。对于一个数组，可以将其从左到右扫描，尝试将较小的元素移动到左边，较大的元素移动到右边。
• 考虑以下策略：以先找到数组中的最小元素，通过以上操作将其移动到数组的第一个位置，然后在剩余的数组中找到最小元素，将其移动到第二个位置，之后重复即可。

  实现

  可以使用两层循环解决题目，外层循环控制要放置的位置，内层循环用于寻找合适的元素并进行操作。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,a[100010];
signed main() {
    scanf("%lld",&t);
    while(t--) {
        scanf("%lld",&n);
        for(int i=1; i<=n; i++) {
            scanf("%lld",&a[i]);
        }
        if(n==1) {
            printf("0\n");
            return ;
        }
        printf("%lld\n",n-1);
        printf("1 %lld\n",n);
        if((a[1]+a[n])%2==0) a[1]=a[n];
        else a[n]=a[1];
        for(int i=2; i<n; i++) {
            if((a[1]+a[i])%2==0) {
                printf("%lld %lld\n",i,n);
            } else {
                printf("1 %lld\n",i);
            }
        }
    }
    return 0;
}