45pts,与时间做斗争
  • 板块P1638 逛画展
  • 楼主sd_JC
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/19 22:17
  • 上次更新2024/10/20 08:34:21
查看原帖
45pts,与时间做斗争
767015
sd_JC楼主2024/10/19 22:17

离谱复杂度

#include<bits/stdc++.h>
using namespace std;
int n,m,a[10000010],b[10000010],minn=0x3f3f3f,l,r;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=01;i<=n;i++)
		scanf("%d",&a[i]);
	auto cl=clock();	
	for(int i=1,ii=n-m-1;i<n-m;i++,ii--){
		memset(b,0,sizeof b);
		for(int j=i;j<n;j++){
			b[a[j]]++;
			int c=0;
			for(int k=1;k<=m;k++)
				c+=(b[k]>0);
			if(c==m){
				if(minn>j-i)
					minn=j-i,l=i,r=j;
				break;
			}
		}
		memset(b,0,sizeof b);
		for(int j=ii;j<n;j++){
			b[a[j]]++;
			int c=0;
			for(int k=1;k<=m;k++)
				c+=(b[k]>0);
			if(c==m){
				if(minn>j-ii)
					minn=j-ii,l=ii,r=j;
				break;
			}
		}
		if((clock()-cl)/100.0>9877)break;
	}
	printf("%d %d",l,r);
    return 0;
}
2024/10/19 22:17
加载中...