题解：P2088 果汁店的难题

junee · 2024-06-27 08:04:25 · 题解

P2088 题解

前置知识

贪心，堆。

题目分析

对于每一种果汁，求出其下一次的位置。当机子个数小于目前个数，则直接放进去；若机子个数等于总个数，则将最远距离的踢掉，先解决近的，再解决远的。

当遇到之前出现过的，将此果汁的距离更新为当前点下一个同样果汁的距离。

Code

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int N=2e5+10;
typedef pair<int,int>PII;
int n,m,k;
int a[N],nex[N],pre[N],b[N];
priority_queue<PII>q;
int ans=0,sz=0;
int main(){
    cin>>k>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        nex[pre[a[i]]]=i;
        pre[a[i]]=i;
    }
    for(int i=1;i<=n;i++)if(!nex[i])nex[i]=0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        if(b[a[i]]){
            q.push({nex[i],a[i]});
            continue;
        }
        if(sz==k)b[q.top().second]=0,q.pop(),sz--;
        b[a[i]]=1;
        q.push({nex[i],a[i]});
        ans++,sz++;
    }
    cout<<ans-k;
    return 0;
}