自动搬运

查看原文

来自洛谷，原作者为

	liunian 不破天道，不回头

搬运于2025-08-24 21:36:18，当前版本为作者最后更新于2019-07-14 12:25:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我看了该题的几篇题解，什么map+set,什么线段树，抱歉我都不会

蒟蒻的方法，大佬勿喷。

实际上只需一个优先队列就能过了，并且跑得贼快。。。。。。

用普通数组存不下1e9，离散就行了。

关于排序的优先级，直接先按照出现的次数排序，再按照时间排序，刚开始打时，我把大于小于弄反了，卡了好几个小时。。。。。。

1. 若内存未被排满，直接将其塞入。

2. 若已排满，其实当前页在不在队列中都不重要，遇到已经存在页就加1即可。因此可以直接通过取队首元素，将其出队直到能够放置时就行了。

直接见我精简但无脑的代码：

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
struct node {
	int xu,t;
	bool operator<(const node &a)const {
		if(t==a.t)return xu>a.xu;
		return t>a.t;
	}
};
priority_queue<node>q;
int a[maxn],b[maxn];
int num[maxn];
int main() {
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1; i<=m; i++)scanf("%d",&a[i]),b[i]=a[i];
	sort(b+1,b+m+1);
	int k=unique(b+1,b+m+1)-b-1;
	int tot=0,ans=0;
	for(int i=1; i<=m; i++) {
		a[i]=lower_bound(b+1,b+k+1,a[i])-b;
		if(num[a[i]])num[a[i]]++,ans++;
		else if(tot<n)tot++,num[a[i]]=1;
		else {
			node res=q.top();
			q.pop();
			while(num[a[res.xu]]!=res.t)res=q.top()，q.pop();
			num[a[i]]++,num[a[res.xu]]=0;
		}
		q.push((node)<%i,num[a[i]]%>);
	}
	printf("%d\n",ans);
	return 0;
}