[백준] 16225 제271회 웰노운컵

문제 링크 : www.acmicpc.net/problem/16225

16225번: 제271회 웰노운컵

문제 유형

Greedy

 

문제 두 개를 선택했을 때, 항상 상대는 B값이 더 큰 문제를 가져간다 했으므로, 주어진 문제들을 B값의 오름차순으로 정렬해 보자.

정렬 후 알 수 있는 사실은 다음과 같다.

즉, 2k + 1 번까지의 문제 중에서 k + 1 개의 문제를 가져갈 수 있고, 이 때 문제를 어떤 조합으로 고르던 항상 배분을 완료할 수 있으므로,

A[i]값이 가장 높은 k + 1개의 문제를 고르면 문제의 정답을 구할 수 있다.

따라서, 2번 문제부터 고를 수 있는 문제의 범위를 2씩 늘려 가며 그때마다 가장 높은 A[i]값을 갖는 문제를 골라 그 A[i]값을 정답에 더해주면 된다.

 

예를 들어, 위의 예시에서 k = 1일 때 고를 수 있는 문제의 범위는 2 ~ 3이다. 따라서, 3번 문제를 고른다.

다음으로 k = 2일 때, 고를 수 있는 문제의 범위는 2 ~ 5이다. 따라서, 5번 문제를 고른다.

k = 3일 때, 고를 수 있는 문제의 범위는 2 ~ 7이다. 따라서, 7번 문제를 고른다.

마지막으로 k = 4일 때, 고를 수 있는 문제의 범위는 2 ~ 9이다. 따라서, 8번 문제를 고른다.

결과적으로 얻을 수 있는 최대 A[i]값의 합은 (2 + 9 + 8 + 6 + 7) = 32 이다.

 

[코드]

최대 A[i] 값을 구하는 데 우선순위 큐를 사용한다. 아래 코드는 시작 인덱스가 0이다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> p;
 
int n, A[200001], B[200001];
vector<p> question;
 
ll greedy() {
    ll ret = question[0].first;        //첫 문제는 반드시 A의 것이 된다.
    priority_queue<int> pque;
    
    for (int i = 1; i < n / 2; i ++) {
        //두 문제를 큐에 삽입
        pque.push(question[2 * i - 1].first);
        pque.push(question[2 * i].first);
 
        //1 ~ 2i + 1(홀수 개) 까지의 문제들 중 가장 A값이 큰 문제를 고른다.
        int top = pque.top();
        ret += top;
        pque.pop();
    }
 
    return ret;
}
 
bool b_asc(p a, p b) {
    return a.second < b.second;
}
 
void init() {
    int a, b;
    cin >> n;
 
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];
    for (int i = 0; i < n; i++) question.push_back({ A[i], B[i] });
 
    //B[i] 오름차순 정렬
    sort(question.begin(), question.end(), b_asc);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    ll answer = greedy();
    printf("%lld\n", answer);
 
    return 0;
}