蒟蒻求助50pts
查看原帖
蒟蒻求助50pts
195331
Mine_KingCattleya楼主2021/7/12 14:16

RT,#3#4#5#6#8 WA,求大佬帮忙调错/kel

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[100005],b[100005];
int ans,nxt[100005],llst[100005];
bool cc[100005];
struct node
{
	int num,lst;
	friend bool operator<(node x,node y)
	{
		return x.lst<y.lst;
	}
};
priority_queue<node>q;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memcpy(b,a,sizeof(b));
	sort(b+1,b+n+1);
	int cnt=unique(b+1,b+n+1)-b;
	for(int i=n;i>=1;i--)
	{
		a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
		if(llst[a[i]]==0) nxt[i]=n+1;
		else nxt[i]=llst[a[i]];
		llst[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&!cc[q.top().num]) q.pop();
		if(cc[a[i]]==true){q.push((node){a[i],nxt[i]});continue;}
		cc[a[i]]=true;
		ans++;
		if((int)q.size()==m)
		{
			cc[q.top().num]=false;
			q.pop();
		}
		q.push((node){a[i],nxt[i]});
	}
	printf("%d\n",ans);
	return 0;
}
2021/7/12 14:16
加载中...