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

 一开始肯定要排个序，b相同时t大的在前边，不同时b大的在前面。

然后想最多只能选k个的限制，可以这样想，每次用到的b只能用已选到的最小的值，那可以把每个b都枚举一遍，然后每一次选时长最长的，且b大于等于当前的b的那k个不就好了吗，时间复杂度也才O（n），然后考虑怎么才能每次快速地选到最大的，这时候就可以考虑优先队列了，每次排序都是logn的复杂度，nlogn，完美。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;const int N = 300010;int n, k;
struct Node
{int a, b;
}songs[N];bool cmp(Node A, Node B)
{if(A.b == B.b)return A.a > B.a;return A.b > B.b;
}int main()
{IOScin >> n >> k;for(int i = 1; i <= n; i ++){cin >> songs[i].a >> songs[i].b;}sort(songs + 1, songs + 1 + n, cmp);//cout << endl;//for(int i = 1; i <= n; i ++)cout << songs[i].a << ' ' << songs[i].b << endl;priority_queue<int, vector<int>, greater<int>> q;ll ans = 0, res = 0;for(int i = 1; i <= n; i ++){if(q.size() < k){q.push(songs[i].a);res += songs[i].a;}else if(songs[i].a > q.top()){res -= q.top();res += songs[i].a;q.pop();q.push(songs[i].a);}ans = max(ans, res * songs[i].b);}cout << ans << endl;return 0;
}

Problem - 1140C - Codeforces