题目链接:https://codeforces.com/contest/1140/problem/C

题意:题意大概是找出至多kk个人使得(ti)×min(bi)(\sum{t_{i}}) \times min(b_{i}) 最大。

题解:这题刚开始想了优先队列,但是都是往大根堆的方向想,但如果是大根堆,那么每次查询都得是kk次很明显是超时的。不妨转换一下思路,用小根堆。首先我们先将playlist从 bib_{i}从大到小排序。那么遍历的时候,无非遇到这两种情况,

(1) 当优先队列里元素小于kk时,很显然,此时将当前元素加入求 maxmax即可。
(2) 当优先队列里元素大于等于kk时,此时,弹出一个最小的bib_{i},将当前元素加入即可,取最大值

思考:为什么弹出的元素不再需要?因为我们刚开始排序是以bib_{i}来排序的,很显然对于某个bib_{i}假设当前弹出的元素对它不需要,那么很显然对于任意bj<=bib_{j} <= b_{i} 很显然也是不需要的

#include <bits/stdc++.h>
#define pa pair<int, int>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 3e5 + 5;
struct node {
    ll t,b;
}a[N];
bool cmp(node a, node b) {
    if(a.b == b.b) return a.t > b.t;
    return a.b > b.b;
}
ll sum[N];
int n,k;
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].t >> a[i].b;
    }
    sort(a + 1, a + n + 1, cmp);
    //puts("");
   /* for(int i = 1; i <= n; i++) {
        cout << a[i].t <<" " << a[i].b << "\n";
    }*/
    ll ans = 0;
    ll sum = 0;
    priority_queue<int, vector<int> ,greater<int> > q;
    for(int i = 1; i <= n; i++) {
        if(q.size() < k) {
            sum += a[i].t;
            q.push(a[i].t);
            ans = max(ans, sum * a[i].b);
        } else {
            sum -= q.top();
            q.pop(); q.push(a[i].t);
            sum += a[i].t;
            ans = max(ans, sum * a[i].b);
        }
    }
    cout << ans;

    return 0;
}