小红的精选笔记

[题目链接](https://www.nowcoder.com/practice/cf57f78b0f334eb0a6be81c1ddea8a8a)

思路

有 篇笔记，第 篇的点赞数为 ，评论数为 。需要选择 篇笔记，使得"优秀度"最大，其中优秀度定义为：

$$

枚举最小值 + 贪心

这类「乘积 = 求和项 × 最小项」的问题，经典做法是枚举最小值。

将所有笔记按评论数从大到小排序。从左到右遍历时，当前笔记的评论数 是已遍历笔记中最小的，可以作为"评论数最小值"的候选。

为了让点赞数之和尽可能大，我们用一个小根堆维护当前已遍历笔记中点赞数最大的 个，同时维护堆中元素之和 ：

  1. 将当前笔记的点赞数加入堆， 加上该值；
  2. 若堆的大小超过 ，弹出堆顶（最小的点赞数）， 减去该值；
  3. 当堆的大小恰好为 时，用 更新答案。

由于笔记按评论数降序排列，遍历到第 个笔记时， 一定是堆中所有笔记评论数的最小值，因此 就是以 为最小评论数时的最大优秀度。

样例演示

输入 ，点赞 ，评论 。

按评论降序排列后的顺序为笔记 2、1、3、4（评论分别为 4、3、2、1）。

步骤 加入笔记 堆中点赞 sum 当前评论 优秀度
1 笔记2 {2} 2 4 堆未满
2 笔记1 {1, 2} 3 3 3×3=9
3 笔记3 {2, 3} 5 2 5×2=10
4 笔记4 {3, 4} 7 1 7×1=7

最大优秀度为 ，对应选择笔记 2 和笔记 3。

复杂度分析

  • 时间复杂度：，排序 ，每个元素至多入堆出堆各一次，每次堆操作 。
  • 空间复杂度：，排序用的索引数组和大小为 的堆。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    vector<int> idx(n);
    for (int i = 0; i < n; i++) idx[i] = i;
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return b[x] > b[y];
    });
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        int j = idx[i];
        pq.push(a[j]);
        sum += a[j];
        if ((int)pq.size() > k) {
            sum -= pq.top();
            pq.pop();
        }
        if ((int)pq.size() == k) {
            ans = max(ans, sum * b[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long[] a = new long[n], b = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        for (int i = 0; i < n; i++) b[i] = sc.nextLong();
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (x, y) -> Long.compare(b[y], b[x]));
        PriorityQueue<Long> pq = new PriorityQueue<>();
        long sum = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            int j = idx[i];
            pq.offer(a[j]);
            sum += a[j];
            if (pq.size() > k) {
                sum -= pq.poll();
            }
            if (pq.size() == k) {
                ans = Math.max(ans, sum * b[j]);
            }
        }
        System.out.println(ans);
    }
}