Codeforces 558B Amr and The Large Array：最小區間保持美麗度不變

題目大意

給定長度為 n 的數組，定義「美麗度」為數組中出現次數最多的數字的頻率。要求找出一個最短子區間 [l, r]，使得該子區間的美麗度等於原數組的美麗度。若有多解，輸出任意一個即可。

核心觀察

設原數組的美麗度為 maxFreq，對應的數字可能有多個。要使子區間美麗度達到 maxFreq，該子區間必須完整包含至少一個達到 maxFreq 的數字的所有出現位置。因此，對於每個候選數字，其最小覆蓋區間就是 [首次出現位置, 最後出現位置]。在所有候選數字中，選擇區間長度最小者即為答案。

算法流程

1. 一次掃描統計每個數字的：出現次數 cnt、首位置 first、末位置 last。
2. 記錄全局最大頻率 maxFreq。
3. 遍歷所有數字，若 cnt == maxFreq，計算區間長度 last - first + 1，維護最小長度及對應區間。
4. 輸出最優區間的 first, last（1-based）。

複雜度

時間 O(n)，空間 O(maxValue)（此處值域 ≤ 10^6，用 unordered_map 或 vector 均可）。

參考代碼（C++）

#include 
using namespace std;
struct Info { int cnt = 0, first = -1, last = -1; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if(!(cin >> n)) return 0;
    vector a(n+1);
    unordered_map mp;
    mp.reserve(n * 2);
    int maxFreq = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        auto &info = mp[a[i]];
        if (info.cnt == 0) info.first = i;
        info.last = i;
        info.cnt++;
        maxFreq = max(maxFreq, info.cnt);
    }
    int bestL = 1, bestR = n, bestLen = n;
    for (auto &[val, info] : mp) {
        if (info.cnt == maxFreq) {
            int len = info.last - info.first + 1;
            if (len < bestLen) {
                bestLen = len;
                bestL = info.first;
                bestR = info.last;
            }
        }
    }
    cout << bestL << ' ' << bestR << '\n';
    return 0;
}

樣例解析

• 5 / 1 1 2 2 1：1 出現 3 次（位置 1,2,5），區間 [1,5] 長度 5；2 出現 2 次。美麗度=3，唯一候選 1，答案 [1,5]。
• 5 / 1 2 2 3 1：1、2 均出現 2 次。1 的區間 [1,5] 長 5；2 的區間 [2,3] 長 2。取較短者 [2,3]。
• 6 / 1 2 2 1 1 2：1、2 均出現 3 次。1 的區間 [1,5] 長 5；2 的區間 [2,6] 長 5。均可，輸出 [1,5]。