[백준] 11963 High Card Low Card (Gold)

Bessis와 Elsie가 카드게임을 한다

카드는 1~N*2까지 있고 그 중 입력으로 주어지는 N개를 Elsie가 가지고 있다

게임의 규칙은 이렇다

Elsie는 입력 순으로 카드를 낸다

처음 N/2판 까지는 카드 숫자가 큰 사람이 이긴다

나머지는 숫자가 작은 사람이 이긴다

카드를 반반 쪼개서 upper_bound를 하면 답을 찾을 수 있다!

처음에는 엘씨의 앞쪽카드 N/2개와 베씨의 뒤쪽카드 N/2

그 다음에는 반대로 하면 된다

소스코드

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int n;
bool used[100005];
int main() {
    scanf(" %d", &n);
    vector<int> a(n),b;
    set<int> B, A;
    for (int i = 0; i < n; i++) {
        scanf(" %d", &a[i]);
        used[a[i]] = true;
        if (i >= n / 2) A.insert(a[i]);
    }
    for (int i = 1; i <= n * 2; i++) {
        if (used[i])    continue;
        if (b.size() != n / 2) b.push_back(i);
        else B.insert(i);
        
    }
    int ans = 0;
    for (int i = 0; i < n / 2; i++) {
        auto pos = B.upper_bound(a[i]);
        if (pos != B.end()) {
            B.erase(*pos); ans++;
        }
        else B.erase(*B.begin());
 
        auto cpos = A.upper_bound(b[i]);
        if (cpos != A.end()) {
            A.erase(*cpos); ans++;
        }
        else A.erase(*A.begin());
    }
    printf("%d\n", ans);
}