双指针 90 #11 TLE 求优化
  • 板块P1638 逛画展
  • 楼主lyliie
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/4 22:55
  • 上次更新2023/10/27 08:46:08
查看原帖
双指针 90 #11 TLE 求优化
411731
lyliie楼主2022/10/4 22:55
#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e6 + 10;
int n, m, a[N], i, j, l, r;
bool v[2010];

inline int read(){
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-')f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
bool check(int l, int r){
	memset(v, 0 ,sizeof(v));
	for(int i = l; i <= r; i ++)
	{
		v[a[i]]=1;
	}
	for(int i = 1; i <= m; i ++)
	{
		if(v[i]==0)return false;
	}
	return true;
}
int main()
{	
	n = read();
	m = read();
	l = 1;
	r = n;
	for(i = 1; i <= n; i ++)
	{
		a[i] = read();
	}
	for(i = 1, j = i + m; i <= n; i ++){
		while(!check(i, j)&&j < n)j ++;
		if(check(i, j) && j - i < r - l)
		{
			l = i;
			r = j;
		}
		if(r - l + 1 == m)break;
	}
	printf("%d %d",l,r);
	return 0;
}
2022/10/4 22:55
加载中...