T229990 题解

每次上课需要对应的书而每次回寝室只能拿一本，身上最多带k本，告诉你上课的顺序后求出最少回寝室的次数。

考虑贪心，显然如果身上满k本书后回寝室拿书一定是把一本下次需要用到的时间最靠后的书换掉。所以就需要求出每本书所需要用到的下一次时间也就是这门课下一次上的时间预先处理出来，然后通过一个优先队列存储身上k本书下一次需要用到的时间，这样就能最快的找到一本下一次用到的时间最靠后的书，然后将它替换掉，最后输出答案。

#include
#define ll long long
using namespace std;
const int mod=1e9+7;
mapmp;//存上课的时间
mapm;//标记当前课的书在不在身上
int ne[100005];//存这门课下一次上的时间
int a[100005];
int n,k;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=n;i>=1;i--){//倒着遍历
		//如果这节课在之后不会在上了
		if(!mp[a[i]]){
			mp[a[i]]=i;//更新这门课上的时间
			ne[i]=99999999;//附一个很大的值表示这门课不会再上了
		}
		//反之这节课在后面还有
		else {
			ne[i]=mp[a[i]];//赋值为下一次这门课上的时间
			mp[a[i]]=i;//更新这门课上的时间
		}
	}
	int ans=0;
	int num=0;//身上书的数量
	priority_queue,less >q;//优先队列
	for(int i=1;i<=n;i++){
		if(!m[a[i]]){//这本书不在身上
			if(num