喵~ 主人，你好呀！今天我们来解决一道非常有趣的题目：F. Longest Strike。这道题就像是在一堆数字里寻找最长的一串连续的小鱼干，而且每种小鱼干的数量都要足够多才行哦！别担心，跟着本喵的思路，一步一步来，很快就能解决它的说！

F. Longest Strike 题目大意

这道题是这样的喵：

首先，我们会得到一个整数数组 a 和一个整数 k。

我们的任务是，找到两个数 l 和 r (其中 l <= r)，它们需要满足下面这个条件：

• 对于从 l 到 r 之间的每一个整数 x（包括 l 和 r），数字 x 在数组 a 中至少出现了 k 次。

在所有满足这个条件的 [l, r] 区间中，我们需要找到一个能让 r - l 的值最大的区间。简单来说，就是找到最长的那个连续数字区间！

如果一个满足条件的区间都找不到，那就孤零零地输出 -1 好了啦。

举个例子，如果 a = [11, 11, 12, 13, 13, 14, 14] 并且 k = 2：

• 区间 [13, 14] 是可以的，因为 13 出现了 2 次，14 也出现了 2 次，都满足至少出现 k=2 次的要求。
• 区间 [12, 14] 就不行了，因为 12 只出现了 1 次，不满足至少出现 2 次的要求。
• 最长的满足条件的区间就是 [13, 14] 啦。

题解方法

想解决这个问题，我们可以分几步走，就像猫猫悄悄接近猎物一样，要有条不紊哦！

1. 统计数量 (Counting is Key!) 首先，我们得知道数组 a 里面每个数字都出现了多少次，对吧？就像数一数我有几条小鱼干一样，喵~ 我们可以用一个 std::map 来帮忙，它会自动帮我们统计好每个数字的个数，而且还会顺便按数字大小排好序，超级方便！

2. 筛选合格的数字 (Filtering the Candidates) 接下来，我们要把那些数量不够的数字踢出去！如果一个数字出现的次数少于 k 次，那它肯定不能在我们最后的 [l, r] 区间里，对不对？所以我们只保留那些出现次数大于等于 k 次的数字，把它们放进一个新的小本本里（比如一个 std::vector）。因为 map 是有序的，所以我们放进 vector 里的数字也自然是从小到大排好序的。

3. 寻找最长连续段 (Finding the Longest Run) 现在我们的小本本里全都是“合格”的数字，而且它们是排好序的。接下来就是最关键的一步啦：在这些合格的数字里，找出最长的一段连续数字！ 比如，我们筛选出的合格数字是 [2, 3, 4, 7, 8, 10]。

   • 2, 3, 4 是一段连续的数字，长度是 4 - 2 = 2。
   • 7, 8 是另一段连续的数字，长度是 8 - 7 = 1。
   • 10 自己是一段。 最长的那段就是 [2, 4]。 我们可以从头到尾扫一遍这个 vector，记录下当前连续段的起点，然后不断检查下一个数字是不是刚好比前一个大 1。如果是，就继续延伸；如果不是，说明这段连续的数字断掉了，我们就结算一下刚刚这段的长度，和我们之前找到的最长长度比较一下，如果更长就更新答案。然后，从当前位置开始寻找下一段。就像猫猫追着毛线球，滚啊滚，直到线断了，就看看这次滚了多远，是不是比上次远，嘻嘻。

4. 特殊情况 (Edge Case) 如果在第一步统计完后，发现没有任何一个数字的出现次数达到了 k 次，那我们的小本本就是空的。这意味着根本找不到任何满足条件的 l 和 r，所以我们直接输出 -1 就好啦。

题解代码 (C++ Code)

这是解题的 C++ 代码，本喵加上了一些注释，方便主人理解哦！

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

void solve() {
    int n, k;
    std::cin >> n >> k;

    // 步骤1：用一个 map 来当我们的记账本，key 是数组里的数字，value 是它出现的次数喵。
    // map 会自动按 key (也就是数字) 排序，超棒的！
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        counts[x]++;
    }

    // 步骤2：把出现次数 >= k 的乖孩子都收集到一个叫 valid_nums 的 vector 里。
    std::vector<int> valid_nums;
    for (auto const& [num, count] : counts) {
        if (count >= k) {
            valid_nums.push_back(num);
        }
    }

    // 步骤4：如果一个合格的数字都没有，那就没办法啦，输出 -1。
    if (valid_nums.empty()) {
        std::cout << -1 << "\n";
        return;
    }

    // 步骤3：寻找最长的连续数字段！
    int best_l = -1, best_r = -1; // 用来记录最终答案的 l 和 r
    int max_len = -1;            // 记录最长的长度 (r - l)

    // `current_start_idx` 记录当前这段连续数字在 `valid_nums` 里的起始下标。
    size_t current_start_idx = 0;
    for (size_t i = 1; i <= valid_nums.size(); ++i) {
        // 什么时候一段连续的数字会结束呢？
        // 1. 已经遍历到 vector 的末尾了 (i == valid_nums.size())
        // 2. 当前数字和前一个数字不连续了 (valid_nums[i] != valid_nums[i - 1] + 1)
        if (i == valid_nums.size() || valid_nums[i] != valid_nums[i - 1] + 1) {
            // 结算刚刚结束的这一段
            int current_l = valid_nums[current_start_idx];
            int current_r = valid_nums[i - 1];

            // 看看是不是比我们之前找到的都长
            if (current_r - current_l > max_len) {
                max_len = current_r - current_l;
                best_l = current_l;
                best_r = current_r;
            }
            
            // 为下一段做准备，新的起点就是当前位置 i
            current_start_idx = i;
        }
    }
    
    // 如果找到了答案，就输出 l 和 r
    std::cout << best_l << " " << best_r << "\n";
}

int main() {
    // 加速一下输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题用到了几个很基础但非常有用的知识点哦，我们来复习一下吧！

1. std::map (映射)std::map 是 C++ STL 里的一个关联容器，它会把放进去的键值对（key-value pair）按照键（key）自动排序。在这里，我们用它来统计数字频率，简直是量身定做！因为 key 是数字，value 是出现次数。它自动排序的特性，保证了我们之后得到的 valid_nums 自然就是有序的，省去了我们自己排序的麻烦，喵~

2. std::vector (动态数组)std::vector 可以看作一个大小可以变化的数组。我们用它来存放所有满足频率要求的数字，因为它的大小可以根据需要动态增长，非常灵活，方便我们进行后续的遍历和检查。

3. 双指针 / 线性扫描思想 在寻找最长连续段的循环里，虽然代码里没有明确写两个指针 left 和 right，但 current_start_idx 和循环变量 i 其实就扮演了类似的角色，圈定了一个“当前正在考察的连续区间”。这种通过移动一个或多个标记来线性扫描处理序列/数组问题的方法，是算法中非常常见和高效的技巧，要好好掌握哦！

4. 贪心思想 (Greedy Approach) 我们的整体策略是：先筛选出所有可能构成答案的数字，然后在这些候选者中，找出最长的连续段。每一步我们都做出了局部最优的选择（找到一个连续段），并期望最终能得到全局最优解（最长的那个连续段）。这种思想就是贪心算法的精髓之一，对于这道题来说，它是正确且高效的！

好啦，这次的题解就到这里啦！主人有没有觉得豁然开朗了呢？只要把问题拆解成一小步一小步，再选择合适的工具，任何难题都能迎刃而解的！下次再见咯，喵~