題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 P6033 [NOIP 2004 提高组] 合并果子 加强版

Problem Statement

題目簡述

給定 nn 堆果子的重量，每次可以選兩堆合併，代價為兩堆重量之和。合併後的新堆重量也是兩堆重量之和。經過 n−1n-1 次合併後只剩一堆，求總代價的最小值。

Constraints

約束條件

  • 1≤n≤1071 \le n \le 10^7
  • 1≤ai≤1051 \le a_i \le 10^5
  • 答案可能超過 32 位整數範圍，需要使用 64 位整數。

思路：Counting Sort + 兩個 Queue

這題的本質是 Huffman 合併：每次從所有堆中取出最小的兩堆合併，代價為兩堆重量之和，合併後的新堆放回去。重複 n−1n-1 次後只剩一堆，求總代價的最小值。

Huffman 貪心的正確性是經典結論：最小的兩堆一定可以放在 Huffman 樹的最深層，先合併它們不會讓答案變差。證明思路是「存在一棵最優樹，最小的兩個葉子互為兄弟」，配合歸納法就能完成。

瓶頸在哪？

在 P1090 [NOIP 2004 提高组] 合并果子 中，nn 最大到 10410^4，O(nlog⁡n)\mathcal{O}(n\log n) 的 Min Heap 操作就能通過。但這裡 nn 最大到 10710^7，O(nlog⁡n)\mathcal{O}(n\log n) 會超時。

Heap 的插入和刪除已經是 O(log⁡n)\mathcal{O}(\log n) 了，還能更快嗎？還是說，這題根本不需要堆？

注意到一個被忽略的條件：每堆重量不超過 10510^5。值域這麼小，意味著我們可以用更輕量的方式來排序。

第一步：用計數排序取代一般排序

值域只有 10510^5，可以直接統計每種重量出現的次數，然後按重量遞增順序，把對應數量的值放入第一個佇列。因為是從小到大放入，這個佇列天然是非遞減的。整個過程就是一次計數排序，時間只有 O(n+D)\mathcal{O}(n + D)，其中 D=105D=10^5 是值域範圍。

值域小時的排序技巧

當輸入數量很大但值域很小時，計數排序是把排序從 O(nlog⁡n)\mathcal{O}(n\log n) 壓到 O(n+D)\mathcal{O}(n+D) 的關鍵。D≤105D \le 10^5 且 n≤107n \le 10^7 時，這幾乎是線性的。

到這一步，原始重量已經排好序了。但問題還沒解決：每次合併後產生的新堆，重量不一定等於任何原始重量，該放在哪裡？

第二步：合併產物的單調性

如果每次合併後都插回原佇列，它不一定在正確的位置——那我們又退化回需要堆的困境了。

不妨觀察合併產物的變化趨勢。第一次合併得到的是當前最小兩堆的和；到了第二次合併，可選的重量只會來自「剩下的原始堆」或「先前產生的新堆」。雖然第一次產生的新堆不一定比所有剩下的原始堆都小，但第二次合併用到的兩個重量，不可能比第一次那兩個更小，因此 第二次合併產生的新堆，一定不會小於第一次合併產生的新堆。

既然合併產物自身就是有序的，我們根本不需要把它們插回原佇列。用第二個佇列獨立保存，每次新產生的堆直接放到這個佇列的隊尾即可。

核心洞察

貪心過程中，每次取出的最小值是單調不減的，因此兩兩相加的結果也是單調不減的。這個「產出天然有序」的性質，讓我們得以用第二個佇列代替堆，把取最小值的代價從 O(log⁡n)\mathcal{O}(\log n) 壓到 O(1)\mathcal{O}(1)。

現在局面變成：兩條各自非遞減的佇列——一條是尚未合併的原始重量，另一條是已經合併產生的新重量。要在這兩條佇列中找全域最小值，只需要比較兩個隊首，取較小者。這其實就是歸併排序中合併兩個有序陣列的操作：每次 O(1)\mathcal{O}(1) 就能拿到最小值。連取兩次，就是 Huffman 貪心需要的「最小的兩堆」。

實作細節

  • 取隊首時要處理其中一個佇列為空的情況。
  • 總代價以及合併產物都要用 64 位整數。n=107n=10^7 時，答案可能遠超 32 位整數範圍。
核心技巧

把 Huffman 合併中「反覆取最小值」的需求，轉成兩條有序流的歸併。第一條有序流來自計數排序（利用了值域小的條件），第二條有序流來自合併產物的單調性（貪心本身的性質）。每次 O(1)\mathcal{O}(1) 比較兩個隊首，總時間 O(n+D)\mathcal{O}(n + D)，在 n=107n=10^7 的規模下也能通過。

複雜度分析

  • 時間複雜度：O(n+D)\mathcal{O}(n + D)，其中 D=105D=10^5 是重量值域。計數排序需要 O(n+D)\mathcal{O}(n + D)，後續 n−1n-1 輪合併每輪 O(1)\mathcal{O}(1)。
  • 空間複雜度：O(n+D)\mathcal{O}(n + D)。計數陣列佔 O(D)\mathcal{O}(D)，兩個佇列合計最多保存 O(n)\mathcal{O}(n) 個元素。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MX = 1e5 + 5;

inline LL read() {
    LL x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

inline void write(LL x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    LL n, x;
    n = read();
    vector<LL> cnt(MX);
    for (int i = 0; i < n; i++) {
        x = read();
        cnt[x]++;
    }
    queue<LL> q1, q2;
    for (int i = 0; i < MX; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            q1.push(i);
        }
    }

    auto pop = [&]() {
        LL res = 0;
        if (q2.empty() || (!q1.empty() && q1.front() < q2.front())) {
            res = q1.front(); q1.pop();
        } else {
            res = q2.front(); q2.pop();
        }
        return res;
    };

    LL ans = 0;
    while (q1.size() + q2.size() > 1) {
        LL x = pop(), y = pop();
        ans += x + y;
        q2.push(x + y);
    }
    write(ans);
    return 0;
}