?一開始肯定要排個序，b相同時t大的在前邊，不同時b大的在前面。
然后想最多只能選k個的限制，可以這樣想，每次用到的b只能用已選到的最小的值，那可以把每個b都枚舉一遍，然后每一次選時長最長的，且b大于等于當前的b的那k個不就好了嗎，時間復雜度也才O（n），然后考慮怎么才能每次快速地選到最大的，這時候就可以考慮優(yōu)先隊列了，每次排序都是logn的復雜度，nlogn，完美。文章來源：http://www.zghlxwxcb.cn/news/detail-658335.html
#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()
{
IOS
cin >> 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文章來源地址http://www.zghlxwxcb.cn/news/detail-658335.html
到了這里，關于Educational Codeforces Round 62 (Rated for Div. 2) C. Playlist的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
