题解：CF1257C Dominated Subarray

HSTYYH · 2025-06-21 16:46:23 · 题解

这是一道贪心的题目。

实际上有可能最短的子序列就是开头和结尾是同一个数，中间都是不同的数字。我们维护整个数列中每个数字 a_i 上一次出现的位置 l_x，则答案为 \min\{i-l_{a_i}+1\}，如果没有这样的值输出 -1 即可。

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

unordered_map<int, int> l;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        int ans = INT_MAX;
        l.clear();
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (l.count(x)) ans = min(ans, i - l[x] + 1);
            l[x] = i;
        }
        cout << (ans == INT_MAX ? -1 : ans) << '\n';
    }
    return 0;
}