题解：CF1257C Dominated Subarray

这是一道贪心的题目。

实际上有可能最短的子序列就是开头和结尾是同一个数，中间都是不同的数字。我们维护整个数列中每个数字

a_i

上一次出现的位置

l_x

，则答案为

\min\{i-l_{a_i}+1\}

，如果没有这样的值输出

-1

即可。

CPP

#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;
}

题解：CF1257C Dominated Subarray

文章操作

相关推荐

评论

题解：CF1257C Dominated Subarray