codeforces 1140c
题目链接:http://codeforces.com/problemset/problem/1140/C
题目大意:
给定n首歌的两个属性length和beauty,需要我们从这n首歌里面找出不超过k首歌,使得选出的歌的length和乘以beauty的最小值的乘积最大。
思路:
这个题里面有两个变量,不好处理。所以我们可以考虑固定其中的一个变量去使得这个乘积最大。
这里我们先按beauty从大到小排序,然后枚举每一个beauty即可到达固定一个变量的效果。我们把枚举过的歌的length都加在sum里,如果当前不足k首歌,那么我们直接加进来处理就好。而如果当前已经满k首歌了,那么我们可以把前面选出的歌里面的length值最小的一首删掉,从而给当前这首歌留出一个空间。考虑到我们只关心最小值,所以可以用一个优先队列来存储所选的歌的length值。具体请参看代码
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
typedef pair<int, int>p;
const int maxn = 1000*100*3 + 10;
ll n,k,a[maxn],b[maxn];
struct node { int a, b; }t[maxn];
bool cmp(node a, node b) {
return a.b > b.b;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> t[i].a >> t[i].b;
}
sort(t+1,t+1+n,cmp);
ll ans = 0;
ll sum = 0;
priority_queue<ll,vector<ll>,greater<ll> >q;
for (int i = 1; i <= n; i++) {
if (q.size() < k) {
q.push(t[i].a);
sum += t[i].a;
ans = max(ans,sum*t[i].b);
}
else {
sum -= q.top(); q.pop();
q.push(t[i].a);
sum += t[i].a;
ans = max(ans,sum*t[i].b);
}
}
cout << ans << endl;
return 0;
}