[Codeforces 1140C]Playlist

[Codeforces 1140C]Playlist

문제 설명 : 

n개의 노래의 length와 beauty가 각각 주어진다. 나는 여기서 최대 k개의 노래를 선택해서 pleasure가 최대가 되도록 해야 하는데, pleasure를 계산하는 공식은 (선택한 노래들의 length들의 합)*(선택한 노래들 중에서 beauty가 가장 작은 값)으로 계산된다.

풀이 : 

우선 beauty를 오름차순으로 정렬한다. 정렬을 하는 이유는 값을 크기 순으로 배치하여 한쪽 방향으로 순회함으로써 하한(lower bound)을 고정할 수 있기 때문이다. 문제에서 pleasure를 계산할 때 어차피 beauty가 가장 작은 값이 무엇인지만 중요하므로, 가장 작은 값을 미리 정해놓음으로써 나머지 노래들은 무조건 그 보다 beauty가 크다는 보장이 되는 것이다. 그런 다음에는 나머지 노래들 중에서 length가 가장 큰 노래들을 찾아야한다. 여기서 필요한 컨테이너가 최소 힙이다. 마지막 인덱스부터(beauty가 큰 순)보면서 현재 노래의 length를 최소 힙에 push한다. 그리고 이 힙에 들어있는 원소들의 합을 저장하는 변수로 sum을 두고 힙에 push할 때마다 sum에도 length를 더해준다. 만약에 힙의 크기가 K보다 커진다면 힙의 top(=힙 안에 있는 원소들 중 가장 원소)를 빼내면 된다. N~1 인덱스마다 이 시행을 반복해주면서 공식에 따라 pleasure를 계산한다.

주의할 점 : 

-

배운 점 : 

으아.. 콘테 때는 풀이까지 거의 다 근접했는데 아쉽게 못 풀었다. 최소 힙까지도 생각했었는데 역순으로 볼 생각을 미처 못했다...ㅠㅠ

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
struct S{
    int l,b;
 
    S(){}
    S(int _l,int _b){
        l=_l;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return b<o.b;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE= 300009;
 
 
S arr[SIZE];
int main(){
    int n,k;    scanf("%d %d",&n,&k);
 
    for(int i=1 ; i<=n; i++){
        int a,b;    scanf("%d %d",&a,&b);
        arr[i]=S(a,b);        
    }
 
    sort(arr+1,arr+1+n);
 
    ll ans=0,sum=0;
    for(int i=n ; i>=1 ; i--){
        mpq.push(arr[i].l);
        sum+=arr[i].l;
 
        if(mpq.size()>k){
            sum-=mpq.top();
            mpq.pop();
        }
        ans=max(ans,sum*arr[i].b);
    }    
    printf("%lld\n",ans);
    return 0;
}