自从ZZZZone吃完糖果后，他开始改吃巧克力了，他每天想吃n个巧克力增在甜蜜值，他决定早上吃K个巧克力，晚上吃n - K个巧克力，每个巧克力在早上吃和在晚上吃的甜蜜值是不一样的，他想让自己得到的甜蜜值最大，并想知道最大是多少。 请你编程帮助他。

这是一个典型的贪心问题，核心思想是：对于每块巧克力，我们应选择它在早上或晚上食用中甜蜜值更高的时段吃；但由于早上最多只能吃 K 块，我们需要在“增益最大”的 K 块巧克力上优先安排它们在早上吃（若早上吃更优），其余安排在晚上吃。

  • 共有 n 块巧克力，编号 1 ~ n。
  • 对第 i 块巧克力：
    • 若早上吃，获得甜蜜值 a[i]
    • 若晚上吃，获得甜蜜值 b[i]
  • 限制：恰好早上吃 K 块，晚上吃 n−K 块（注意：不是“最多”，是“恰好” K 块）。
  • 目标：最大化总甜蜜值。

若题目说“早上吃 K 个，晚上吃 n−K 个”，通常隐含 恰好 K 个。如果题目特别说明“最多 K 个”，那么代表允许少于 K 个，

解题思路

第一步：基准方案

假设所有巧克力都在晚上吃(全部在早上吃也同理)，此时早上吃了 0 块，还需额外安排 K 块改到早上吃。

第二步：考虑“改到早上”的增益

若将第 i 块从晚上改到早上，甜蜜值变化Δ_i > 0：改到早上更优

  • 若 Δ_i < 0：改了反而亏，但可能被迫改（因为必须恰好改 K 块）

第三步：贪心选择

要恰好改 K 块，使总增益最大 → 选择 Δ_i 最大的 K 个巧克力改到早上。

即：

  1. 计算所有 Δ_i = a[i] - b[i]
  2. 按 Δ_i 从大到小排序
  3. 取前 K 个的 Δ 之和，加到 base 上

示例验证

假设 n = 3, K = 1

i a[i]（早） b[i]（晚） Δ = a−b
1 5 3 +2
2 4 4 0
3 1 6 −5
  • base = 3 + 4 + 6 = 13
  • Δ 排序：[+2, 0, −5] → top1 = +2
  • answer = 13 + 2 = 15

🧾 代码实现

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    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];

    // 基准：全晚上吃
    long long total = 0;
    vector<long long> delta(n);
    for (int i = 0; i < n; ++i) {
        total += b[i];
        delta[i] = a[i] - b[i];
    }

    // 降序排序 Δ
    sort(delta.begin(), delta.end(), greater<long long>());

    // 加上前 K 大的增量
    for (int i = 0; i < K; ++i) {
        total += delta[i];
    }

    cout << total << '\n';
    return 0;
}

复杂度分析

  • 时间：O(n log n)（排序主导）
  • 空间：O(n)

若 n 极大（如 1e7），可用 priority_queue优化到O(n log K)或者nth_element 优化到 O(n)，但通常 n ≤ 2e5，O(n log n) 足够。

注意

对于此类题目我更倾向于使用优先队列，但是需要注意的是优先队列默认是最大堆(C++中)，最小堆需要额外的说明 std::priority_queue<int, std::vector<int>, std::greater<int>> pq_min;（vector在指定比较器时必须显式提供，greater为标准库自带，当然也支持自己写）

std::nth_element 是C++ 标准库中的一个算法，原型如下：

  // 想让 [0, K) 包含最大的 K 个（无序），[K, n) 是剩下的
nth_element(delta.begin(), delta.begin() + K, delta.end(), greater<long long>());

功能： 重排 [first, last) 中的元素，使得： *nth 是整个区间排序后的第 nth - first 小的元素（即“第 k 小”被放到位置 k）。 所有在 [first, nth) 的元素 ≤ *nth 所有在 [nth, last) 的元素 ≥ *nth 但不保证 [first, nth) 或 [nth, last) 内部有序。 （注意：默认是升序划分，即左边 ≤ pivot ≤ 右边）