题目:
见https://www.luogu.com.cn/problem/P1638
思路:
我以为我这么做会超时来着,没想到ac了,具体思路就是:为了满足题目要求即花最少的钱,那么我们就二分区间长度,如果在该长度下满足题意,那么就缩短长度,反之就增加长度,至于如何判断是否满足呢,可以想象一个定长的窗口从左往右滑动,每次就判断窗口内的元素种类是否等于m即可,注意二分区间取大点,不然有个样例一直过不了!!!
代码:
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e6+10;
const int M=2e3+10;
int a[N],n,m,t=1e10;
typedef pair<int,int> PII;
int check(int mid,queue<PII> q,int *visit)
{
int temp=0;
for(int i=1;i<=n;i++)
{
if(!visit[a[i]])
temp++;
visit[a[i]]++;
q.push({i,a[i]});
if(q.size()==mid&&temp==m)
{
t=q.front().first;
return 1;
}
if(q.size()==mid&&temp<m)
{
int t1=q.front().first;
int t2=q.front().second;
q.pop();
visit[t2]--;
if(visit[t2]==0)
temp--;
}
}
return 0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
int l=m-1,r=n+1;//又得加大二分区间
while(l<r)
{
int visit[M]={0};//这个visit和queue最好是开在循环里,不然很麻烦
queue<PII> q;
int mid=l+r>>1;
if(check(mid,q,visit)) r=mid;
else
l=mid+1;
}
cout<<t<<" "<<t+l-1<<endl;
return 0;
}