[Codeforces][Round #693][Div.3] D : Even-Odd Game (C++)

https://codeforces.com/contest/1472/problem/D

Problem - D - Codeforces

 

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

[풀이]
홀수, 짝수인 숫자를 따로 vector에 보관 후 정렬하고,
Alice 차례일때 현재 홀수중 최댓값이 짝수중 최댓값보다 크다면 홀수를 선택해서 Bob이 선택못하도록 하고,
짝수가 더크다면 짝수를 선택하는 방식으로 하는것이 Alice에게 최적이다.
Bob의 차례인 경우엔 그 반대로 하면 된다.

다른 풀이를 보고 알 수 있었는데
홀수,짝수 상관없이 정렬 후 큰 수부터 선택해도 Alice,Bob 모두 optimal 하므로 이 방식으로 풀어도 된다.

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
int tc,N;
int main(){
    scanf("%d",&tc);
    
    while(tc--){
        scanf("%d",&N);
        vector<ll> odd,even;
        for(int i=0;i<N;i++){
            ll v;
            scanf("%lld",&v);
            if(v%2) odd.push_back(v);
            else even.push_back(v);
        }
        sort(odd.begin(),odd.end());
        sort(even.begin(),even.end());
        
        int curo=odd.size()-1,cure=even.size()-1;
        ll alice=0,bob=0;
        for(int i=0;;i++){
            if(curo<0&&cure<0) break;
            if(i%2==0){
                if(curo<0){
                    alice+=even[cure--];
                    continue;
                }
                if(cure<0){
                    curo--;
                    continue;
                }

                if(odd[curo] <= even[cure]){
                    alice+=even[cure--];
                }else{
                    curo--;
                }
            }else{
                if(curo<0){
                    cure--;
                    continue;
                }
                if(cure<0){
                    bob+=odd[curo--];
                    continue;
                }

                if(odd[curo] >= even[cure]){
                    bob+=odd[curo--];
                }else{
                    cure--;
                }
            }
        }
        if(alice>bob) puts("Alice");
        else if(alice<bob) puts("Bob");
        else puts("Tie");
        //printf("alice:%d, bob:%d\n",alice,bob);
    }
}

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