题解：CF2167C Isamatdin and His Magic Wand!

WizeBug · 2025-12-15 15:50:18 · 题解

codeforces 传送门

洛谷传送门

题意概括

给定 T 组测试样例，每组样例包含一个长度为 n 的整数序列。可以执行仅交换奇偶性不同的两个元素的操作，要求找出通过这种操作能得到的字典序最小的序列。

解题思路

分两种情况：

1. 如果数组中既有奇数又有偶数：由于存在至少一对奇偶性不同的元素，我们可以将任意两个元素交换位置。例如：想要要交换两个奇数 a_1 和 a_2，可以先交换 a_1 和一个偶数 a_3，再交换 a_2 和 a_3，最后再交换 a_1 和 a_3，这样就实现了 a_1 和 a_2 的交换。因此，在这种情况下，我们可以对整个数组进行任意重排，所以直接排序就能得到字典序最小的排列。
2. 如果数组中全是奇数或全是偶数：无法进行任何交换（因为所有元素的奇偶性相同），故数组保持原样。

   代码实现

   AC 记录

   #include<bits/stdc++.h>
   using namespace std;
   const int N=2e5+1;
   int T,n,a[N];
   bool ji=0,ou=0;
   int main(){
   ios::sync_with_stdio(0);    cin.tie(0); cout.tie(0);
   cin>>T;
   while(T--){
       cin>>n;
       ji=0,ou=0;  //多测清空。
       for(int i=1;i<=n;i++){  //统计奇偶性。
           cin>>a[i];
           if(a[i]%2)  //存在奇数。
               ji=1;
           else        //存在偶数。
               ou=1;
       }
       if(ji && ou)    //同时存在奇数与偶数。
           sort(a+1,a+n+1);
       for(int i=1;i<=n;i++)
           cout<<a[i]<<' ';
       cout<<'\n';
   }
   return 0;
   }