CF1545A AquaMoon and Strange Sort - crazy-

CF1545A AquaMoon and Strange Sort

题目传送门

题意

有 \(n\) 个人从左到右站成一排，从左数第 \(i\) 个人的衣服上印着 \(a_i\)。每个人的朝向可以是朝左、朝右。一开始所有人的方向都是朝右。

您可以对这些人做一些“操作”，每次操作允许您找两个相邻的人让他们交换顺序，但是在操作之后，两人都会掉头，也就是朝向都从朝右变成朝左或者相反。

现求是否存在一种操作方法使得操作完成后这 \(n\) 个人衣服上的数字 \(a_1, a_2, \ldots , a_n\) 从左往右读单调不减，并且最后所有人的方向都朝右。

思路

联想一下，会发现这题很像一个冒泡排序，每个数都有一个目标位置，需要通过交换相邻的数来到达

那么特征也就出来了，为了使他的方向不变，所以他的位置之差一定是偶数，换句话说，就是在新序列和旧序列中，同一个数的位置奇偶性一致

这道题的一个难点在于如何判断相同的数，这里参考一下题解思路，用\(f_i\)表示旧序列中数字\(i\)位于偶数位置的个数，\(g_i\)表示位于奇数位置的个数。

而在新的序列里，也存在这样一组\(f\)和\(g\)，现在且叫他们\(f'\)和\(g'\)

那么，条件就变为了\(f_i=f'_i\)且\(g_i=g'_i\)

据此写出代码即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=1e5+10;
int a[Maxn];
int f[Maxn],g[Maxn];
int flag,n;
void run()
{cin>>n;flag=1;memset(f,0,sizeof(f));memset(g,0,sizeof(g));for(int i=1;i<=n;i++){cin>>a[i];f[a[i]]+=(i%2==0);g[a[i]]+=(i%2==1);}sort(a+1,a+n+1);for(int i=1;i<=n;i++) f[a[i]]-=(i%2==0),g[a[i]]-=(i%2==1);for(int i=1;i<=n && flag;i++) if(f[a[i]] || g[a[i]]) flag=0;cout<<(flag?"Yes":"No")<<endl;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--) run();system("echo. & pause");return 0;
}