特别的玛格丽特

NC234762. 特别的玛格丽特

描述

special margaret.

特别的玛格丽特。

给定一个数组。每次可以交换数组中两个奇数或者两个偶数，可以交换无数次。问最后是否能把数组变成非降序数组？

用数学语言来说，对于数组 $a$ ，每次可以交换 $a_i$ 和 $a_j$ ，当且仅当 $i≠j$ 且 $(a_i-a_j)\ mod\ 2=0$ 。问经过一些操作后，最终是否能使得数组满足：对于 $i∈[1,n)$ ， $a_i\leq a_{i+1}$ ？

输入描述

第一行输入一个正整数  ，代表数组的长度。
第二行输入  个正整数  ，代表拿到的数组。

输出描述

如果最终能使数组变成非降序，则输出"Yes"。否则输出"No"。

示例1

输入:

5
3 2 1 4 5

输出:

Yes

示例2

输入:

5
1 3 2 2 5

输出:

No

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 412K, 提交时间: 2022-03-10 19:02:33

#include<bits/stdc++.h>
using namespace std;
int n,a[103],b[103];
int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i],b[i]=a[i];
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i){
		if((a[i]^b[i])&1){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
}

Python3 解法, 执行用时: 42ms, 内存消耗: 4592K, 提交时间: 2022-03-10 19:02:47

n=int(input())
a=[*map(int,input().split())]
b=sorted(a)
ans=1
for i in range(n): 
    if (a[i]^b[i])&1: 
        ans=0
print(["No","Yes"][ans])