题解：P14131 【MX-X22-T2】「TPOI-4B」K Problem

解题思路

模拟，把所以可能的

k

都列举一遍。

可以得出这个区间的长度

len=\dfrac{k\times(k+1)}2

。然后，对于所有长度为

len

的区间判断元素个数是否合法。注意，这里的枚举区间的元素个数必须像滑动窗口一样，右边进左边出，否则会导致时间复杂度过大。

这里的

k

的最大值在

450

以下（因为

\dfrac{450\times451}2>10^5

）。我在赛时直接使

k=\max\limits_{i=1}^na_i

，痛失

\text{20 pts}

。

Code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010],b[100010],n;
bool pd(int mid)
{
	for(int i=1;i<=mid;i++)
		if(b[i]!=i)return 0;
	return 1;
}
bool ck(int x)
{
	memset(b,0,sizeof b);
	int len=(x+1)*x/2;
	for(int i=1;i<=n;i++)
	{
		b[a[i]]++;
		if(i>len)b[a[i-len]]--;
		if(i>=len&&pd(x))return 1;
	}
	return 0;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	BREAK:
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=450;i>=1;i--)
			if(ck(i))
			{
				cout<<i<<'\n';
				goto BREAK;
			}
		cout<<"0\n";
	}
	return 0;
}

题解：P14131 【MX-X22-T2】「TPOI-4B」K Problem

文章操作

解题思路

Code

相关推荐

评论

题解：P14131 【MX-X22-T2】「TPOI-4B」K Problem