题解 P2088 【果汁店的难题】

loi_wzhd · 2017-10-31 18:40:41 · 题解

非常抱歉，管理员同志，刚刚代码交错了，可以帮忙把楼下那篇删掉吗？不胜感激。

贪心的思路为：当我们所有榨汁机都没有清洗时我们要选之后出现最晚的进行清洗。

模拟：案例一波堆模拟的做法，对于优先级比较高的，无脑压入堆，每次取出优先级最高的（出现最晚的）进行清洗，当堆顶为一个已经无效的元素时，直接丢弃。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,las[205],nex[205],used[205],ans,num[205];
struct zt
{
    int ys,yxj;
    bool operator < (const zt &a) const 
    {
        return a.yxj > yxj;
    }
};
priority_queue<zt>q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i ++)
        scanf("%d",&num[i]);
    memset(las,0x3f,sizeof(las));
    for(int i = m;i >= 1;i --)
    {
        nex[i] = las[num[i]];
        las[num[i]] = i;
    }
    for(int i = 1;i <= m;i ++)
    {
        if(used[num[i]]) {q.push((zt){num[i],nex[i]});continue;}
        if(q.size() >= n)
        {
            while(!q.empty()&&!used[q.top().ys]) q.pop();
            ans ++;
            if(!q.empty()) used[q.top().ys] = 0,q.pop();
            else ans --;
        }
        q.push((zt){num[i],nex[i]});
        used[num[i]] = 1;
    }
    printf("%d",ans);
}