题解：CF1733C Parity Shuffle Sorting

题目传送门

思路

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

实现

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

代码

CPP

#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;
}

题解：CF1733C Parity Shuffle Sorting

文章操作

题目传送门

思路

实现

代码

相关推荐

评论

题解：CF1733C Parity Shuffle Sorting