Educational Codeforces Round 62 (Rated for Div. 2) - C Playlist

当时题意看错了。。。不过大致思路是对的，唯一没有想到的就是用优先队列搞这个东西，真是不该啊。。。

题意大概就是，有N首歌，N首歌有两个东西，一个是长度Ti，一个是美丽值Bi，你最多可以选择K首歌，

这些首歌的总和是这些歌的总的长度乘以其中最大的美丽值。

简而言之，就是选择最K个点，问其第一权值总和乘以最小第二权值最大时多少？

很容易想到需要把第二权值排序。

举个例子

4 3

4 7

15 1

3 6

6 8

排序后

T 15 3 4 6

B 1 6 7 8

我们发现，如果我选择了第一个，我需要在剩下的中找到k-1个第一个权值最大的数，并求和。

同样的，我们如果选择了第二个，那么第一个一定是不能选的，我们也是需要在剩下的数中找到前k-1个第一权值最大的数，并求和。

想到这里，离成功就很近了，但是我就没想下去，就觉得已经不可能了。。。

我们不妨这样考虑，如果我逆向枚举呢？？？

我从N-K+1开始，那么第K个一定被选，后K-1个也一定必选对吧？

如果我从N-K开始，那么第K-1个一定被选，后K个中我们找到其中的前K-1个第一权值大的数？

如果我从N-K-1开始，那么第K-2个一定被选，后K个中我们找到其中前K-1个第一权值大的数？

关键问题在，如何每次维护前K-1个第一权值大的数，而且还要维护其和？

那么优先队列便呼之欲出了，首先维护后K项的和，每次往后选择的时候，这时优先队列有K个值，我们需要把，优先队列中，最小的给那走，并加上当前必选的第二权值，再维护和。这样优先队列里面一直维护的从从枚举点后K-1个最大值。但是需要注意的是，题意是要求最多K个，那么我们再把后k项的值再最开始一并维护就行了。

#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<queue>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define LL long long
using namespace std;
const int maxx = 3e5+6;
struct node
{
    int t,b;
} a[maxx];
bool cmp(node x,node y)
{
    if (x.b==y.b)
    {
        return x.t<y.t;
    }
    return x.b<y.b;
}
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {

        for (int i=1; i<=n; i++)
        {
            scanf("%d%d",&a[i].t,&a[i].b);
        }
        sort(a+1,a+1+n,cmp);
        LL sum=0;
        LL ans=0;
        per(i,n,n-k+1)
        {
            q.push(a[i].t);
            sum+=(LL)a[i].t;
            ans=max(ans,sum*a[i].b);
        }
        if (k<n)
        {
            LL num;
            per(i,n-k,1)
            {
                sum-=q.top();
                sum+=(LL)a[i].t;
                q.pop();
                q.push(a[i].t);
                num=(LL)sum*a[i].b;
                ans=max(ans,num);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}