题目描述

难度分:$1600$

输入$n$，$k(1 \leq k \leq n \leq 3 \times 10^5)$和$n$个物品，每个物品输入两个属性值$t[i]$和$b[i]$，范围 $[1,10^6]$。

从这$n$个物品中选出至多$k$个物品，输出这$k$个物品的$sum(t) \times min(b)$的最大值。

输入样例$1$

4 3
4 7
15 1
3 6
6 8

输出样例$1$

78

输入样例$2$

5 3
12 31
112 4
100 100
13 55
55 50

输出样例$2$

10000

算法

反悔贪心

这种题目的做法非常经典，一般要求最大值那就对其中的一个属性降序排列，先贪这个属性的最大值。然后试图减小这个属性，增加另一个属性，从而增加目标函数的值。

初始化答案$ans=0$，选择的物品$t$属性之和为$sum$，先对物品数组$playlist$按照$b$属性降序排列，然后遍历$playlist$，当遍历到$playlist[i]$时，$playlist[i].b$就是目标函数中的$min(b)$。先无脑选择这个物品，将$playlist[i].t$放入小根堆，然后有如下两种情况：

1. 如果此时堆中的元素个数（就是选择的物品）不超过$k$，那就直接更新此时的目标函数最大值。
2. 否则就需要换出一个贡献最小的物品，由于在选择$playlist[i]$时$min(b)$已经减小了，因此我们希望换出去的$playlist[i]$的$t$属性最小，这样$sum$那一项不会有很大损失，弹出堆顶的$t$即可，此时先更新$sum=sum-heap.top()+playlist[i].t$，然后用$sum \times playlist[i].b$来更新答案。之所以$playlist[i].b$不需要变是因为如果小根堆$pop$掉的不是新加入的$playlist[i].t$，那显然$min(b)=playlist[i].b$，弹出堆顶后的答案就是$(sum-heap.top()+playlist[i].t) \times playlist[i]$；如果小根堆$pop$掉的是新加入的$playlist[i].t$，那就相当于啥也没干，而啥也没干的$sum(t) \times min(b)$是否能更新答案已经在遍历到$playlist[i]$之前考虑过了，此时的$sum(t) \times playlist[i].b$是无法更新$ans$的，不用管。

这样遍历一遍数组$playlist$就能得到最大的目标函数。

复杂度分析

时间复杂度

遍历一遍数组，每遍历到一个物品时，会往堆中压入元素，时间复杂度是$O(log_2n)$的，因此整体算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

除去输入数据的空间，空间的瓶颈就是堆的消耗。最差情况下堆中会存入$O(n)$级别的元素数量，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
typedef long long LL;

const int N = 300010;
int n, k;
struct node {
    LL t, b;
    bool operator<(const node other) const {
        return b > other.b;
    }
} playlist[N];

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld", &playlist[i].t, &playlist[i].b);
    }
    sort(playlist + 1, playlist + n + 1);
    priority_queue<int, vector<int>, greater<int>> heap;
    LL ans = 0, sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += playlist[i].t;
        heap.push(playlist[i].t);
        if(heap.size() > k) {
            sum -= heap.top();
            heap.pop();
        }
        ans = max(ans, sum*playlist[i].b);
    }
    printf("%lld\n", ans);
    return 0;
}