[HOJ]28 看動畫

貪心

對於每次抽換都換掉離目前最遠的點
若已經在裡面了要更新

#include<cstdio>
#include<set>
#include<vector>
#include<functional>
#include<utility>
#define MAX 100005
using namespace std;
int n,p,k,tmp,a[5*MAX],t,pos[MAX];
set<pair<int,int> > s;
vector<int> v[MAX];
int main(){
    scanf("%d%d%d",&n,&k,&p);
    for(int i=0;i<p;i++){
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
    }
    for(int i=0;i<=n;i++)v[i].push_back(1000000000);
    for(int i=0;i<p;i++){
        if(s.find(make_pair(-v[a[i]][pos[a[i]]],a[i]))!=s.end()){
            s.erase(make_pair(-v[a[i]][pos[a[i]]],a[i]));
            s.insert(make_pair(-v[a[i]][++pos[a[i]]],a[i]));
            continue;
        }
        if(s.size()>=k){
            s.erase(s.begin());
            t++;
        }
        s.insert(make_pair(-v[a[i]][++pos[a[i]]],a[i]));
    }
    printf("%d\n",t);
}