C.Dominated Subarray

题目：受主导的子序列##

题意：序列t至少有2个元素，我们称序列t被数字出现次数最多的元素v主导，且出现次数最多的元素必须是唯一的

你被给予了序列a1, a2, ..., an，计算它的最短受主导子序列，或者说这里没有这种序列

[4, 1, 2, 4, 5, 4, 3, 2, 1]的最短受主导子序列为[4, 5, 4]

链接:(受主导的子序列)[https://codeforces.com/contest/1257/problem/C]

分析：我们可以检查每个相同数字(受主导的元素)的对，求出它们之间的距离，然后在每对距离里取最小值

但是可以有更好的方法，时间复杂度为O(n)，我们可以从头开始检查元素，如果出现相同的元素，就求出它们之间的距离，然后将后面的元素作为下一段开始受主导子序列的开头。

证明：每段受主导子序列是两两分明，且里面没有两端相同的元素，否则则会产生更短的受主导子序列

#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 2e5 + 5;

const int INF = 0x3f3f3f3f;

vector<int> a;

void solve()

{

	int n;

	cin >> n;

	a.resize(n + 1);

	for (int i = 0; i < n; ++i)

		cin >> a[i];

	if (n == 1)

	{

		cout << -1 << endl;

		return;

	}

	int ans = INF;

	vector<int> lst(n + 1, -1);//n + 1个 -1

	for (int i = 0; i < n; i++) {

		if (lst[a[i]] != -1)

			ans = min(ans, i - lst[a[i]] + 1);

		lst[a[i]] = i;

	}

	if (ans > n)

		ans = -1;

	cout << ans << endl;

	a.clear();

	lst.clear();

}

int main()

{

	int T;

	cin >> T;

	for (int i = 1; i <= T; ++i)

	{

		solve();

	}

	return 0;

}

巴特西

C.Dominated Subarray

题目：受主导的子序列##

最新文章

热门文章