求调双指针awa
  • 板块P1638 逛画展
  • 楼主canwen
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/19 13:54
  • 上次更新2024/8/19 15:58:45
查看原帖
求调双指针awa
1284815
canwen楼主2024/8/19 13:54

rt,我双指针老烂了awa。

81 pts,#1 WA,#11 TLE。

#include<bits/stdc++.h>
using namespace std;

/*
100 15
13 2 8 1 9 7 7 9 1 13 14 11 14 9 7 14 1 7 13 11 13 9 9 8 3 1 12 10 1 6 3 6 14 2 8 9 1 12 3 8 8 14 4 12 12 4 7 6 4 12 15 10 2 3 14 1 12 6 6 3 9 1 2 9 7 4 2 11 2 12 7 4 7 1 8 6 15 8 8 9 5 7 3 4 9 15 5 5 11 13 7 15 6 2 2 12 15 4 5 2 

*/
const int N=1e6+5;
const int NN=2e3+5;
int n,m,s[N],w[NN],rp,ansl,ansr,ans=1e9;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>s[i];
	int l=1,r=0;
	while(l<=n-m){
		int cnt=0;
		while(r<n&&cnt<m){
			r++;
			w[s[r]]++;
			if(w[s[r]]==1) cnt++;
		}
		while(l<r&&w[s[l]]>1) w[s[l]]--,l++;
		if(cnt==m&&r-l+1<=ans) ans=r-l+1,ansl=l,ansr=r;
		rp++;
		l=rp,r=rp;
		memset(w,0,sizeof(w));
	}
	cout<<ansl<<" "<<ansr<<"\n";
	return 0;
}
2024/8/19 13:54
加载中...