必威体育Betway必威体育官网
当前位置:首页 > IT技术

果汁店的难题

时间:2019-07-04 15:43:30来源:IT技术作者:seo实验室小编阅读:66次「手机版」
 

果汁店

题目描述

炎热的夏天,来上一杯现榨的冰爽果汁想想都是一件惬意的事情!话说小王就看准了这一商机,在学校附近开了这么一家果汁店,但是最近他碰到了一个不大不小的难题:小王的果汁店里准备了K台榨汁机,当然每台榨汁机只能榨一种果汁,在某个时段内,一个客人点了某种果汁,如果恰好有某台果汁机榨过这种果汁,那么就直接给客人用这台果汁机接着榨就可以了,但是如果点的是一种新的果汁就需要找一台干净的果汁机来用,问题就出在这,如果这时候还有空的果汁机还好,如果没有的话小王就需要将某台刚才用过的拿去清洗,清洗的话呢就得浪费很多的时间和很多的水,小王是个很有经济头脑的人,他想知道在排队客人需求已知的情况下最少需要清洗多少次果汁机?假定开始时所有果汁机都是干净的,为了方便描述,我们将果汁编号为1(橙汁),2(苹果汁),3(葡萄汁)…

[友情提示:本店不售卖混合果汁]

输入输出格式

输入格式:

每组测试数据第一行包括两个整数K,N(1<=K<=10,1<=N<=100), 其中,K表示小王准备了K台干净的榨汁机,N表示排队等待的有N个客人,接下来N行,每行一个整数表示一个客人点的果汁种类Xi(1<=xi<=100).

输出格式:

输出在当前的请求序列下,小王最少需要清洗果汁机的次数

#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);
}

相关阅读

一道产品面试题:小明要喝果汁,妈妈没空,怎么解决?(续集)

昨天我发表《一道产品面试题:小明要喝果汁,妈妈没空,怎么解决?》,我没想到这道有趣的题目能一下引爆了评论区,短短20h,就突破过万的阅读

一道产品面试题:小明要喝果汁,妈妈没空,怎么解决?

偶然看到的一道产品经理面试问答:小明要喝果汁,妈妈没空,怎么解决?看到这个题目时,就引起了我无限的遐想和好奇心(内心os:这是一道相当有

果汁饮料营销策划,如何找到吸引消费者的亮点

果汁饮料,首先想到的是可口可乐、百事可乐、汇源等,这就是品牌的力量。果汁品牌营销策划,是规划战略意义,如何有效吸引消费者成为核心

椰子怎么打开喝汁,教你几个小诀窍,不用打开椰子就可以喝

椰子怎么打开?教你几个小诀窍,不用打开椰子就可以喝到果汁!

分享到:

栏目导航

推荐阅读

热门阅读