Educational Codeforces Round 62 (Rated for Div. 2)C. Playlist（优先队列）

题意

给n首歌，最多选择其中的k个，每首歌有一个长度t和美丽度b，你的愉悦度是你选择的歌曲的总长度*这些歌曲中美丽度最小的那个数。

思路:

给这n首歌按歌的美丽度从大到小排序，从前往后遍历。
每次我们把我们当前的这首歌的长度塞进优先队列（从小到大）如果长度大于k，队首出列，当前的愉悦度就是队列中所有元素的总和*当前这首歌的美丽度。为什么呢？？因为我们是按歌曲的愉悦度从大到小排序的，那么我们当前的愉悦度肯定是我们队列里面最小的那个愉悦度，然后我们又是让队列中最小的先出队，即保证队列里面的sum总是前i个的最大值，那么答案不就是a[i].w * sum么。考虑如果我们当前的这个t是一个很小的t,且队列已经被塞满，是不是肯定会被pop出去，而且当前的w肯定不会比前一个大，所以我们一路更新下来ans，肯定不会错。//嘻嘻

#include<cstdio>
#include<cstring>
#include "algorithm"
#include "cmath"
#include<queue>
using namespace std;
const int maxn=300005;
#define mod 1000000007
#define inf 0x3f3f3f3f
#define ll long long
struct node {
    ll t,w;
}a[maxn];
bool cmp(node a,node b){
    return a.w>b.w;
}
priority_queue<ll,vector<ll>,greater<ll> >q;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].t,&a[i].w);
    sort(a+1,a+1+n,cmp);
    ll ans,sum;
    ans=0;sum=0;
    for(int i=1;i<=n;i++){
        q.push(a[i].t);
        sum+=a[i].t;
        while(q.size()>k){
            sum-=q.top();
            q.pop();
        }
        ans=max(ans,sum*a[i].w);
    }
    printf("%lld\n",ans);
    return 0;
}
/*
 4 3
 4 7
 15 1
 3 6
 6 8

 */