按美麗度從大到小排序
從大到小跑一遍美麗度。随着i的增加,美麗度在減少。在美麗度減少的同時,在保證長度的個數為k個的情況下盡可能讓長度變長,求得每次美麗度和長度和的乘積,取最大的那個。
/*
* codeforces1140C Playlist
* 有一個播放清單裡n首歌,第i首歌長度ti,美麗度bi。
* 聽整個歌曲集合的爽度=min(bi)*Σ(ti)。
* 你可以從清單裡選最多k首歌,使它們構成集合的爽度最大。
* 輸出爽度
*/
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
#define all(x) (x).begin(),(x).end()
const int MAX = 300000 + 5;
typedef long long ll;
pair<int, int> a[MAX];
priority_queue<int> pq;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
return p1.second > p2.second;
}
int main() {
ios::sync_with_stdio(false);
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i].first >> a[i].second;
}
//pair的預設排序規則是first從小到大排序,當first相等時second從小到大排序
sort(a, a + n, cmp);
//在該題目中也就是美麗度second從大到小排序
for (int i = 0; i < n; i++) {
cout << a[i].first <<" "<< a[i].second<<endl;
}
ll ans = 0, now = 0;
//随着i的增加,美麗度在減少。在美麗度減少的同時,
//在保證長度的個數為k個的情況下盡可能讓長度變長,
//求得每次美麗度和長度和的乘積,取最大的那個。
for (int i = 0; i < n; i++) {
now += a[i].first;
//加上目前的長度
pq.push(-a[i].first);
//将長度取反加入優先隊列,這樣隊頭的元素為長度最小的值的取反。
if(pq.size()>k){
now+=pq.top();
//實際上是把長度最小的減去了。
pq.pop();
}
ans=max(ans,now*a[i].second);
//在循環的同時美麗度已經變成了這些長度中的最小美麗度。
}
cout<<ans<<endl;
return 0;
}