自动搬运

查看原文

来自洛谷，原作者为

	CW666 **

搬运于2025-08-24 21:59:49，当前版本为作者最后更新于2019-08-20 15:50:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

函数解释：

      unique（）[unique函数的解释](https://www.cnblogs.com/wangkundentisy/p/9033782.html)
	  
      make_pair（a,b)(过于无法理解我自行解释）将a与b压进堆里。a可以用于大根堆的排序
		
      lower_bound（）[lower_bound函数的解释](https://baike.baidu.com/item/lower_bound/8620039?fr=aladdin)

unique与lower_bound处理完减去数组可以得到处理后的址 （在下面代码有体现）

//方法：如果该容器已满，后来出现的不在容器中的，一定要由容器中的元素中距离下一次出现最远的那个元素来替换掉。 代码挺明确了就直接看吧

#include <bits/stdc++.h>//万能头文件 
using namespace std;//使用命名空间吧ei 
const int INF=0x3fffffff;//定义 
int a[100005],b[100005],last[100005],next[100005],cnt,sum;//定义 
bool vis[100005];//定义 
//用next[i]数组保存第I个内存地址的下一次出现的位置
//last[i]表示 下一次对i的 操作
// vis数组标记当前值是否在堆中
priority_queue <pair<int,int> > h; //建大根堆 
int n,m;//定义 
int main() { //main函数 
	memset(next,1,sizeof(next));//初始化 
	scanf("%d%d",&n,&m);//输入 
	for(int i=1; i<=n; i++) {//循环
		scanf("%d",a+i);//输入 
		b[i]=a[i];//赋值 
	}//结束循环 
	sort(b+1,b+1+n);//排序 
	int num=unique(b+1,b+1+n)-b-1;//去重,离散化，从后往前建出每块主存的操作顺序，返回最右址 
	for(int i=1; i<=n; i++)  {//循环
		a[i]=lower_bound(b+1,b+1+num,a[i])-b;//寻找第一个>=a[i]的数，返回址 
		next[last[a[i]]]=i;//构建 next数组 
		last[a[i]]=i;//构建last数组 
	}//结束循环 
	for(int i=1; i<=n; i++) { //循环 
		while(!h.empty()&&!vis[h.top().second]) h.pop();//如果大根堆不是空的并且堆顶元素的a[i]不在Cache缓存里就删除堆顶元素 
		if(vis[a[i]]) h.push(make_pair(next[i],a[i]));//如果a[i]在Cache缓存里就push进当前点的next[i]值 
		else{//如果a[i]不在Cache里 
			cnt++;//答案++ 
			vis[a[i]]=1;//a[i]标记 
			if(!h.empty()&&sum>=m) {//如果大根堆不是空的并且缓存没有剩余;
				vis[h.top().second]=0;//将堆顶元素的a[i]标记 
				h.pop();//删除堆顶元素 
			}//结束判断 
			if(sum<m) //如果Cache容量有剩余 
				sum++;//缓存++ 
			h.push(make_pair(next[i],a[i]));//把当前点push进去 
		}//结束否则 
	}//结束 循环 
	printf("%d",cnt); //输出答案 
	return 0; //功德圆满 
}//结束main函数 

言简意赅