백준 23750 - Leader-based Team Distribution

https://www.acmicpc.net/problem/23750

23750번: Leader-based Team Distribution

[알고리즘 분류]

Greedy

 

 

 꽤 웰노운 그리디인 것 같다. 가장 중요한 관찰은 \(L_i\)가 가장 높은 사람이 무조건 리더가 된다는 것과, 여기에서 어떤 사람을 팀에 할당해도 리더는 변하지 않는 것이다. 그러면 이 성질을 활용하여, 계속하여 적절한 \(L_i\)를 뽑아보자.

 

 \(L_i, P_i\)에 대해 내림차순으로 정렬하자. \(1\)번째 사람은 \(1\)번째 팀의 리더가 될 수 밖에 없다. 그 후, 인덱스가 구간 \([2, T_1 + 1]\)에 속하는 사람들 중 \(P_i\)가 가장 큰 사람을 뽑는다. 이 사람은 \(2\)번째 팀의 리더가 된다. 일단 이게 왜 되는지는 직관적이게 알 수 있다.

 두번째 팀의 리더를 빨간 점들 중에서 뽑는다면, 초록색 네모칸에 해당하는 사람의 \(L_i\) 값이 더 클 때 문제가 된다. 이 사람이 리더가 되지 않는다는 것이 보장되지 않기 때문이다. 즉 구간 \([T_j + 1, T_{j+1} + 1]\)에 해당하는 사람들을 후보에 추가하고, 여기서 \(P_i\)의 값이 가장 큰 사람을 뽑으면 된다.

 

 또한 후보의 수는 많을수록 이득이므로, 배열 \(T\) 또한 내림차순으로 정렬해야 한다.

 

 후보에 사람을 추가하고, 삭제하는(리더를 뽑는) 과정은 우선순위 큐를 사용해 간단히 구현할 수 있으며, 시간복잡도는 \(O(NlogN)\)이므로 시간 안에 동작한다.

 

 발상의 과정이 이 문제와 비슷하다고 느꼈다.

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
 
//const ld eps = 1e-9;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
 
#define all(v) v.begin(),v.end()
#define X first
#define Y second
#define endl '\n'
 
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr)
 
// end of def
 
int n,m;
pii a[333333];
int t[333333];
 
 
int main() {
    fastio;
    cin>>n>>m;
    priority_queue<pii> pq;
    for (int i=0;i<n;i++)cin>>a[i].X>>a[i].Y;
    for (int i=0;i<m;i++)cin>>t[i];
    sort(a,a+n);
    reverse(a,a+n);
    sort(t,t+m);
    reverse(t,t+m);
    ll ans = 0;
    int j=1;
    pq.emplace(a[0].Y, a[0].X);
    for (int i=0;i<m;i++){
        ans += pq.top().X; pq.pop();
        for (int k=0;k<t[i];k++){
            pq.emplace(a[j+k].Y,a[j+k].X);
        }
        j+=t[i];
    }
    cout<<ans<<endl;
    return 0;
}