题解

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;

int main() {
// 读取输入
int N, K;
cin >> N >> K;
vector<int> breeds(N);
for (int i = 0; i < N; i++) {
cin >> breeds[i];
}

// 初始化哈希表和多重集合
unordered_map<int, int> freq;  // 记录每种血统的出现次数
multiset<int> freqs;           // 维护所有血统的出现次数，用于快速获取最大频率
int left = 0;                  // 滑动窗口的左指针
int ans = 0;                   // 记录最大连续段长度

// 滑动窗口遍历
for (int right = 0; right < N; right++) {
    int b = breeds[right];     // 当前奶牛的血统编号

    // 更新当前血统的频率
    if (freq.find(b) != freq.end()) {
        // 如果血统已存在，先从多重集合中删除其旧频率
        auto it = freqs.find(freq[b]);
        freqs.erase(it);
    }
    freq[b]++;                 // 增加当前血统的频率
    freqs.insert(freq[b]);     // 将新频率插入多重集合

    // 当窗口内血统种类超过 K+1 时，移动左指针
    while (freq.size() > K + 1) {
        int b_left = breeds[left];
        // 从多重集合中删除左指针所指血统的旧频率
        auto it = freqs.find(freq[b_left]);
        freqs.erase(it);
        freq[b_left]--;        // 减少左指针所指血统的频率
        if (freq[b_left] == 0) {
            // 如果频率归零，从哈希表中移除该血统
            freq.erase(b_left);
        } else {
            // 否则，将新频率插入多重集合
            freqs.insert(freq[b_left]);
        }
        left++;                // 移动左指针
    }

    // 更新答案：取当前窗口内出现次数最多的血统的频率
    if (!freqs.empty()) {
        ans = max(ans, *freqs.rbegin());
    }
}

// 输出结果
cout << ans << endl;
return 0;

}