HDU 5210 Delete：貪心策略最大化剩餘數字種類

問題描述

給定 N（≤100）個整數（值域 1~N），需刪除 K 個數，使剩餘數字的**不同值的個數**最多。多組測試數據。

貪心洞察

為保留盡可能多的不同數字，應優先刪除**出現次數 > 1** 的數字。具體步驟：

1. 統計每個數字的出現次數 cnt[v]。
2. 將所有 cnt[v] 降序排序。
3. 計算「多餘數字總數」 sum = Σ(cnt[i] − 1)。
4. 若 K ≤ sum，說明只需刪除多餘部分，答案為不同數字個數 distinct。
   否則，答案為 distinct − (K − sum)（不低於 0）。

正確性證明

刪除一個重複數字不會減少種類數；只有當所有數字都只剩 1 個時，進一步刪除才會犧牲種類。貪心策略正是盡量避免犧牲種類。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N) {
        vector cnt(N + 1, 0);
        for (int i = 0, x; i < N; ++i) {
            cin >> x;
            if (x <= N) cnt[x]++;
        }
        int K; cin >> K;
        vector freq;
        for (int v = 1; v <= N; ++v)
            if (cnt[v]) freq.push_back(cnt[v]);
        sort(freq.begin(), freq.end(), greater());
        int distinct = freq.size();
        int extra = 0;
        for (int c : freq) extra += c - 1;
        int ans = (K <= extra) ? distinct : max(0, distinct - (K - extra));
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(N log N) 主要來自排序，N ≤ 100 極輕鬆通過。