【第70题】提升递推功力：Codeforces 1848 - B. Vika and the Bridge，和跳石头蛮像的一道题

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
 
using namespace std;
#define endl '\n';
 
void best_coder() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        int n, k;
        cin >> n >> k;
        vector<int> last(k + 1, -1);
        vector<vector<int>> max_num(k + 1, vector<int>(2, -1));
        vector<int> v(n);
        for (int j = 0; j < n; ++j) {
            cin >> v[j];
            if (j - last[v[j]] - 1 > max_num[v[j]][0]) {
                max_num[v[j]][1] = max_num[v[j]][0];
                max_num[v[j]][0] = j - last[v[j]] - 1;
            } else if (j - last[v[j]] - 1 > max_num[v[j]][1]) {
                max_num[v[j]][1] = j - last[v[j]] - 1;
            }
            last[v[j]] = j;
        }
        for (int j = 1; j <= k; ++j) {
            if (n - last[j] - 1 > max_num[j][0]) {
                max_num[j][1] = max_num[j][0];
                max_num[j][0] = n - last[j] - 1;
            } else if (n - last[j] - 1 > max_num[j][1]) {
                max_num[j][1] = n - last[j] - 1;
            }
        }
        int ans = 0x3f3f3f3f;
        for (int j = 1; j <= k; ++j) {
            ans = min(ans, max(max_num[j][0] / 2, max_num[j][1]));
        }
        cout << ans << endl;
    }
}
 
void happy_coder() {
}
 
int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    // 小码匠
    best_coder();
 
    // 最优解
    // happy_coder();
 
    // 返回
    return 0;
}