题目链接:https://codeforces.ml/contest/1556/problem/B
当时卡了一个半小时硬是不会做orz
思路:统计n个数中奇偶数的个数,可分四种情况:若abs( odd - even ) > 1说明无解,若 odd == even ,则分别计算奇数在偶数位和偶数在奇数位需要交换的次数。这里可以只计算将奇数 / 偶数归位所需要交换的次数即可。然后取一个最小值。若 odd > even 则一定是奇数在奇数位出现,若 odd < even 则是偶数在奇数位出现。
ac代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long LL;
LL a[N];
int n,t;
int main(){
ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i];
int cnto = 0,cnte = 0;
for(int i = 1;i <= n;i++)
if(a[i]&1)cnto++;
else cnte++;
if(abs(cnto-cnte)>1)cout << -1 << endl;
else{
int mino = 0,mine = 0,cto = 0,cte = 0;
for(int i = 1;i <= n;i++)
if(a[i]&1)mino+=abs(i - cto*2 - 1),cto++;
for(int i = 1;i <= n;i++)
if((a[i]&1)==0)mine+=abs(i - cte*2 - 1),cte++;
if(cnto == cnte){
cout << min(mino,mine) << endl;
}
else if(cnto == cnte+1)cout << mino << endl;
else {
cout << mine << endl;
}
}
}
return 0;
}
p.s. 注意&运算符的优先级比==低,套上括号。