UVA 11714 Blind Sorting：比較樹高度與信息論下界

問題描述

給定 n 個互不相同的數，只能通過兩兩比較。求在最壞情況下，找出最大值和第二大值所需的最少比較次數。

信息論下界與比較樹

每次比較獲得 1 bit 信息。要確定最大值和第二大值，相當於在 n 個元素中找出最大和次大。
已知結論：最少比較次數 = n - 1 + ⌈log₂ n⌉ - 1 = n + ⌈log₂ n⌉ - 2。

推導過程

1. 找最大值：錦標賽法，n-1 次比較。形成一棵比較樹，根為最大值，葉為原始元素。
2. 找第二大值：第二大值必定曾直接輸給最大值（否則傳遞性下會有更大值）。最大值參與了 ⌈log₂ n⌉ 場比較（樹高），故最多有 ⌈log₂ n⌉ 個候選者。
3. 從候選者中找最大：需 ⌈log₂ n⌉ - 1 次比較。
4. 總計：(n-1) + (⌈log₂ n⌉ - 1) = n + ⌈log₂ n⌉ - 2。

C++ 代碼

#include 
#include 
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        int ans = n - 1 + (int)ceil(log2(n)) - 1;
        printf("%d\n", ans);
    }
    return 0;
}

樣例驗證

關鍵洞察

此題不需模擬比較過程，直接套用「比較樹高度 = ⌈log₂ n⌉」的結論。體現了「信息論下界 + 對手論證」在比較模型中的應用。注意 log2 需包含 cmath，ceil 返回 double 需轉 int。