[Codeforces] CF1733C Parity Shuffle Sorting

题面翻译

给定一个长度为 \(n\) 的数组，你可以对它进行不超过 \(n\) 次操作。

对于每次操作：

• 选择两个下标 \(l, r\)，满足 \(1\leq l<r\leq n\)；
• 若 \(a_l + a_r\) 为奇数，将 \(a_r\) 赋值为 \(a_l\)，否则将 \(a_l\) 赋值为 \(a_r\)。

求一种方案，使得操作后的数组单调不减（即 \(a_1\leq a_2\leq a_3 \leq \cdots\leq a_n\)）。

思路

可以发现，只要一段数形如：

\(k,a_1,a_2,...a_n,k\)，那么通过若干次操作，他一定能够变得全部相等

所以这道题只需要在一开始对第\(1\)和第\(n\)位进行一次操作，让着两个位置相等，那整个序列肯定也能变的相等了

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1e5+10;
int n;
int a[Maxn];
void run()
{
    vector<pair<int,int> >ans;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if((a[1]+a[n])%2==1) a[n]=a[1];
    else a[1]=a[n];
    if(n-1) ans.push_back(make_pair(1,n));
    for(int i=2;i<n;i++)
    {
        if(a[i]==a[1]) continue;
        else if((a[i]+a[1])%2==1) ans.push_back(make_pair(1,i));
        else ans.push_back(make_pair(i,n));
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--) run();
    return 0;
}