题意

• 有一段长为n的整数序列，一个长为m的空间，遍历整数序列，如果空间中没有该元素就需要将该元素加入，如果空间满了就需要移除一些元素，问遍历完整个序列最少需要多少次加入操作

思路

• 贪心思考，满了以后移除出现最晚的，因为出现的最晚，所以占位时间长，造成的损失更大
• 如果按照出现次数最多贪心，会发现对于长为2的空间序列{1，2，3，2，3，2，3，2，3，1，1，1，1，1，1，1}，如果按出现次数最多的贪心答案是9，但是按照最晚进行贪心答案为4，所以按照出现次数最多贪心是不正确的
• 维护一个大顶堆，队列记录空间中元素下一次出现的时间，如果堆满了，就让弹出堆顶，同时，记录堆顶元素已不在空间
• 元素进入堆后标记同值的下一个元素，如果堆中已经有了当前元素就将下一次出现时间弹入，因为下一次时间一定大于当前时间，所以当前时间不会造成影响；

AC代码

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

int a[101010],nxt[101010],us[101010];
//a读入，nxt记录下一个同值元素位置，us记录当前元素是否在空间中
map<int,int> mp;//将记录每一个值的下一个位置
priority_queue<int,vector<int>,less<int>>b;//记录空间中m个元素下一次的出现时间

int main(){
	int n,m,y=0,ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mp[a[i]]=0;
	}
	for(int i=n;i>0;i--){
		if(mp[a[i]]==0) nxt[i]=101010-1;
      //最后一个的下一个是整个列表的最后一个位置
		else nxt[i]=mp[a[i]];
		mp[a[i]]=i;
	}
	for(int i=1;i<=n;i++){
		if(us[i]==0){//不在，ans++
			ans++;
			if(y<m){//没存满
				y++;
				us[nxt[i]]=1;//对下一个标记，记录为已在空间中
				b.push(nxt[i]);
			}else{
				us[b.top()]=0;//弹出后把下一个记录为不在队列中
				b.pop();
				b.push(nxt[i]);//把当前的下一个入队
				us[nxt[i]]=1;//当前的下一个标记为在空间中
			}
		}else{//已经在了，更新下一次出现的时间
			us[nxt[i]]=1;
			b.push(nxt[i]);
		}
	}
	printf("%d\n",ans);
	return 0;
}