[TIOJ] 1221. 炒菜問題 / [POI] XII. Toy Cars
題目連結:http://tioj.infor.org/problems/1221或POI XII Toy Cars
我不知道怎麼證明QAQ...
總之做法就是要移掉東西的時候,就挑接下來最晚出現的移掉。而要維護誰最晚出現我這裡是開個陣列先預處理好對於每個$i$,紀錄下一個跟他一樣的數字是在哪裡。而接著掃過去的時候,每走到一個地方,就把這個地方的更新掉,這要樣pop東西的時候就可以拿到最新的資訊了。
我不知道怎麼證明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;
}
留言
張貼留言