社区讨论

63分求助

P1638逛画展参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo1ir3c1
此快照首次捕获于
2023/10/22 21:43
2 年前
此快照最后确认于
2023/11/02 22:37
2 年前
查看原帖
使用单调队列的思想。
WA了后四个点。
CPP
//2023/9/5
//别着急,先通读一遍题目
//别忘了开long long
//写完先看一遍怎么降复杂度
//要么开全局变量要么给定初值
//想想看,有什么情况需要特判
//看看数组开的够不够大
//std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans;
int a[MAXN],vis[MAXN];
queue<int> que;
int main()
{
	int n,m,u,v;
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	int r=1,l=1;
	while(num<m){
		if(vis[a[r]]==0) num++;
		vis[a[r]]++;
		que.push(r);
		r++;
	}
	ans=r-1;
	v=ans;
	u=que.front();
	while(que.size()&&vis[a[que.front()]]>1){
		vis[a[que.front()]]--;
		que.pop();
		ans--;
		u=que.front();
	}
	int res=ans;
	for (int i=r;i<=n;i++){
		que.push(i);
		vis[a[i]]++;
		res++;
		while(que.size()&&vis[a[que.front()]]>1){
			//cout<<"ssdas"<<endl;
			vis[a[que.front()]]--;
			que.pop();
			res--;
			if(res<ans){
				u=que.front();
				v=i;
			}
		}
	}
	cout<<u<<" "<<v<<endl;
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...