Codeforces1140C.Playlist(思维)

题目链接:Codeforces1140C.Playlist

题意:

给定n对数,从中最多选k对数,要求选出的数的xi之和与min(yi)的乘积最大。

题解:

考虑对yi排序,然后用小顶堆维护xi,开始贪心,先按yi的大小顺序把元素加入堆中,用sum记录堆中xi之和,然后当堆中元素大于k时,弹出最小的xi,sum中也减去相xi,然后计算答案取最大。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
struct node
{
    ll t, b;
} a[300005];
bool cmp(node x, node y)
{
    if (x.b == y.b)
        return x.t > y.t;
    return x.b > y.b;
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i].t >> a[i].b;
    sort(a + 1, a + 1 + n, cmp);
    priority_queue<ll, vector<ll>, greater<ll>> q;
    while (!q.empty())
        q.pop();
    ll sum = 0, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        q.push(a[i].t);
        sum += a[i].t;
        if (q.size() > k)
            sum -= q.top(), q.pop();
        ans = max(ans, 1ll * sum * a[i].b);
    }
    cout << ans;
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。