[Codeforces][Round #650][Div.3] B : Even Array (C++)

https://codeforces.com/contest/1367/problem/B

[난이도] Div.3
[유형] Greedy

[풀이]
0~N-1까지 확인하면서 i번에서 Good을 만족하지 않으면
i+1~N-1까지의 j를 확인하면서 a[i]가 j에 들어갔을 때 Good을 만족하면서
a[j]가 i에 들어갔을 때도 Good을 만족하면 swap해주는 방식으로 몇번을 swap해줘야 하는지를 세준다.
만약 바꿀 수 있는 j가 없으면 답이 없으므로 -1을 출력한다.

 

#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
int tc,N,a[41];
int sol(){
    int cnt =0;
    for(int i=0;i<N;i++){
        if(a[i]%2==i%2) continue;
        bool ok = 0;
        for(int j=i+1;j<N;j++){
            if(i%2==a[j]%2 && j%2==a[i]%2){
                swap(a[i],a[j]);
                cnt++;
                ok=1;
                break;
            }
        }
        if(!ok) return -1;
    }
    return cnt;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=0;i<N;i++) scanf("%d",&a[i]);
        printf("%d\n",sol());
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round650-Div.3/B.cpp