CF2167C 学习笔记

本蒟蒻的第五篇题解，求管理员通过。

正题

题意

给定一个长度为 \(n\) 的序列 \(\{a_n\}\)，你可以用以下操作使此数列字典序最小：

• 任选两个下标 \(1 \le i,j \le n\) 且 \(a_i\) 和 \(a_j\) 奇偶性相同，交换这两个数。

分析

显然，整个数列从小到大排序时字典序最小，考虑数列中有两个数 \(a_i\) 和 \(a_j\) 需要交换：

• 若这两个数奇偶性不同，直接交换即可；
• 若这两个数奇偶性相同，若数列中存在一个与这两个数奇偶性不同的数 \(a_k\)，则先交换 \(a_i\) 和 \(a_k\)，再交换 \(a_k\) 和 \(a_j\) 即可完成这两个数的交换。

用两个 \(flag\) 标记数列中是否有奇数和偶数即可。

代码

#include <iostream>
#define maxn 200005 // 好习惯
using namespace std;int t, n;
int a[maxn];
bool flag1, flag2;int main() {cin >> t;while (t--) {flag1 = flag2 = false;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++)if (a[i] % 2 == 1)flag1 = true;elseflag2 = true; // 统计if (flag1 && flag2) {sort(a + 1, a + n + 1);for (int i = 1; i <= n; i++)cout << a[i] << ' '; // 排序后输出}else for (int i = 1; i <= n; i++)cout << a[i] << ' '; // 直接输出}return 0;
}