[TIOJ] 1221. 炒菜問題 / [POI] XII. Toy Cars

題目連結:http://tioj.infor.org/problems/1221或POI XII Toy Cars

---

我不知道怎麼證明QAQ...
總之做法就是要移掉東西的時候，就挑接下來最晚出現的移掉。而要維護誰最晚出現我這裡是開個陣列先預處理好對於每個$i$，紀錄下一個跟他一樣的數字是在哪裡。而接著掃過去的時候，每走到一個地方，就把這個地方的更新掉，這要樣pop東西的時候就可以拿到最新的資訊了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define FF first
#define SS second
const int N = 500000 + 5;
const int M = 100000 + 5;

map<int,int> mp;
int nxt[N], tmp[M], arr[N];
bool ins[M];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, k, p; cin>>n>>k>>p;
	for(int i=0;i<p;i++) nxt[i] = p+i;
	for(int i=0;i<=n;i++) tmp[i]=-1;
	for(int i=0;i<p;i++) cin>>arr[i];
	for(int i=0;i<p;i++){
		if(tmp[arr[i]]!=-1) nxt[tmp[arr[i]]] = i;
		tmp[arr[i]]=i;
	}
	int size = 0, ans = 0;
	for(int i=0;i<p;i++){
		if(!ins[arr[i]]){
			if(size == k){
				ins[mp.rbegin()->SS]=0; size--;
				mp.erase(mp.rbegin()->FF);
			}
			ans++;
			mp.insert({nxt[i], arr[i]});
			ins[arr[i]]=1; size++;
		}
		if(mp.find(i)==mp.end()) continue;
		mp.erase(i);
		mp.insert({nxt[i], arr[i]});
	}
	cout<<ans<<'\n';
	return 0;
}