题解 | #小红的精选笔记#

题目链接

小红的精选笔记

题目描述

小红有 $n$ 篇笔记，每篇笔记有 $a_i$ 个点赞和 $b_i$ 个评论。

她需要选择 $k$ 篇笔记组成一个“精选笔记合集”。

合集的优秀程度定义为：（所选 $k$ 篇笔记的点赞数总和） $\cdot$ （所选 $k$ 篇笔记的评论数中的最小值）。

目标是找到一种选择方案，使得合集的优秀程度最大。

解题思路

这是一个最优化问题。目标函数是 总点赞数 * 最小评论数。直接枚举所有选择 $k$ 篇笔记的组合（ $C_n^k$ 种）是不可行的。

我们可以转换思路。优秀度的计算涉及一个最小值，这通常是一个很好的突破口。我们可以枚举每一篇笔记，假设它就是我们所选合集中评论数最少的那一篇。

核心思想

如果我们确定了合集中评论数最少的笔记是第 $i$ 篇（其评论数为 $b_i$ ），那么为了让 最小评论数 这个因子尽可能大，我们选择的其他 $k-1$ 篇笔记的评论数都必须大于等于 $b_i$ 。

在所有评论数不少于 $b_i$ 的笔记中，为了让 总点赞数 这个因子最大，我们应该贪心地选择其中点赞数最高的 $k$ 篇（当然，第 $i$ 篇笔记自身也必须是这 $k$ 篇之一）。

优化算法

基于以上思想，我们可以设计一个高效的算法：

排序：

将所有笔记按照 评论数从高到低 进行排序。如果评论数相同，可以按点赞数从高到低排序（这有助于提早找到更优解，但非必需）。这个排序是关键，它保证了当我们在数组中从左到右遍历时，当前笔记的评论数总是小于或等于之前所有笔记的评论数。
遍历与维护：

我们从头到尾遍历排序后的笔记数组。对于遍历到的第 $i$ 篇笔记（设其点赞为 $a_i$ ，评论为 $b_i$ ），我们考虑一个以它为“评论数瓶颈”的合集。

此时，所有可选的笔记就是从第 $1$ 篇到第 $i$ 篇。因为我们是按评论数降序排列的，所以这 $i$ 篇笔记的评论数都大于或等于 $b_i$ 。

在这个包含 $i$ 篇笔记的“候选池”中，我们需要选出点赞数最高的 $k$ 篇。为了高效地做到这一点，我们可以使用一个大小固定为 $k$ 的 最小堆（Min-Heap）。
使用最小堆：
- 遍历排序后的笔记数组。
- 对于当前笔记的点赞数 $a_i$ ：
  - 将其加入最小堆。
  - 同时，累加当前堆内所有元素的和 current_likes_sum。
  - 如果堆的大小超过了 $k$ ，就弹出堆顶的最小元素，并从 current_likes_sum 中减去这个值。这样，堆里始终保留着到目前为止遇到的前 $k$ 大的点赞数。
- 当堆的大小恰好达到 $k$ 时，我们就形成了一个有效的 $k$ 篇笔记合集。此时：
  - 最小评论数 就是当前笔记的评论数 $b_i$ （因为数组是按 $b_i$ 降序的）。
  - 总点赞数 就是 current_likes_sum。
  - 计算 优秀度 = current_likes_sum * b_i，并用它来更新全局的最大优秀度。
最终结果：

遍历完所有笔记后，记录下的最大优秀度就是答案。

代码

cpp
java
python

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

using namespace std;

struct Note {
    long long likes;
    long long comments;
};

bool compareNotes(const Note& a, const Note& b) {
    if (a.comments != b.comments) {
        return a.comments > b.comments;
    }
    return a.likes > b.likes;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    int k;
    cin >> n >> k;

    vector<Note> notes(n);
    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];

    for (int i = 0; i < n; ++i) {
        notes[i] = {a[i], b[i]};
    }

    sort(notes.begin(), notes.end(), compareNotes);

    long long max_excellence = 0;
    long long current_likes_sum = 0;
    priority_queue<long long, vector<long long>, greater<long long>> min_heap;

    for (int i = 0; i < n; ++i) {
        min_heap.push(notes[i].likes);
        current_likes_sum += notes[i].likes;

        if (min_heap.size() > k) {
            current_likes_sum -= min_heap.top();
            min_heap.pop();
        }

        if (min_heap.size() == k) {
            max_excellence = max(max_excellence, current_likes_sum * notes[i].comments);
        }
    }

    cout << max_excellence << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;
import java.util.PriorityQueue;

class Note implements Comparable<Note> {
    long likes;
    long comments;

    public Note(long likes, long comments) {
        this.likes = likes;
        this.comments = comments;
    }

    @Override
    public int compareTo(Note other) {
        if (this.comments != other.comments) {
            // 降序
            return Long.compare(other.comments, this.comments);
        }
        // 降序
        return Long.compare(other.likes, this.likes);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Note[] notes = new Note[n];
        long[] a = new long[n];
        long[] 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();

        for (int i = 0; i < n; i++) {
            notes[i] = new Note(a[i], b[i]);
        }

        Arrays.sort(notes);

        long maxExcellence = 0;
        long currentLikesSum = 0;
        PriorityQueue<Long> minHeap = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            minHeap.add(notes[i].likes);
            currentLikesSum += notes[i].likes;

            if (minHeap.size() > k) {
                currentLikesSum -= minHeap.poll();
            }

            if (minHeap.size() == k) {
                maxExcellence = Math.max(maxExcellence, currentLikesSum * notes[i].comments);
            }
        }

        System.out.println(maxExcellence);
    }
}

import sys
import heapq

def solve():
    try:
        n, k = map(int, sys.stdin.readline().strip().split())
        likes = list(map(int, sys.stdin.readline().strip().split()))
        comments = list(map(int, sys.stdin.readline().strip().split()))
    except (IOError, ValueError):
        return

    notes = sorted(zip(comments, likes), reverse=True)
    
    max_excellence = 0
    current_likes_sum = 0
    min_heap = []

    for comment, like in notes:
        heapq.heappush(min_heap, like)
        current_likes_sum += like
        
        if len(min_heap) > k:
            popped_like = heapq.heappop(min_heap)
            current_likes_sum -= popped_like
            
        if len(min_heap) == k:
            excellence = current_likes_sum * comment
            if excellence > max_excellence:
                max_excellence = excellence
                
    print(max_excellence)

solve()

算法及复杂度

算法：贪心 + 排序 + 优先队列（最小堆）
时间复杂度： $O(N \log N)$ 。
- 将笔记按评论数排序需要 $O(N \log N)$ 。
- 遍历所有笔记需要 $N$ 步，每一步对优先队列进行操作（插入和可能的删除）需要 $O(\log K)$ 。这部分总共是 $O(N \log K)$ 。
- 整体复杂度由排序主导，为 $O(N \log N)$ 。
空间复杂度： $O(N)$ 。
- 需要 $O(N)$ 的空间来存储笔记对象数组用于排序。
- 优先队列需要 $O(K)$ 的空间。
- 总空间复杂度为 $O(N)$ 。