HDU 3785 尋找大富翁：Top-M 查詢的高效實現

題目大意

烏鎮有 n 人 (n ≤ 100,000)，每人有一筆財產值。需快速找出前 m 富翁 (m ≤ 10)，財產多者優先。多組測試數據，以 0 0 結束。

算法選擇

由於 m 極小 (≤10)，無需複雜的堆或選擇算法。直接全量排序後取尾部 m 個元素即可，時間複雜度 O(n log n)，常數極小，極易實現且足夠快。

實現細節

• 使用 sort 升序排列
• 若 n < m，輸出全部；否則輸出最後 m 個
• 注意輸出格式：空格分隔，行末換行

優化代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int a[MAXN];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
        sort(a, a + n);
        int start = max(0, n - m);
        for (int i = n - 1; i >= start; --i) {
            printf("%d%c", a[i], i == start ? '\n' : ' ');
        }
    }
    return 0;
}

關鍵點

1. 讀入條件 while (scanf(...)==2) 配合 n==0&&m==0 終止
2. 排序後從後向前輸出，自動滿足「財產多者在前」
3. 邊界處理：max(0, n-m) 統一處理 n<m 和 n≥m 兩種情況

這道題看似簡單，實則考察對題目約束條件（m 很小）的敏銳觀察，避免過度設計複雜數據結構。