外卖店优先级蓝桥杯第十届

首页 » 算法 » 外卖店优先级蓝桥杯第十届

“饱了么”外卖系统中维护着 N 家外卖店,编号 1 ∼ N。每家外卖店都有
一个优先级,初始时 (0 时刻) 优先级都为 0。
每经过 1 个时间单位,如果外卖店没有订单,则优先级会减少 1,最低减
到 0;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5,则会被系统加入优先缓存中;如果
优先级小于等于 3,则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息,请你计算 T 时刻时有多少外卖店在优
先缓存中。
【输入格式】
第一行包含 3 个整数 N、 M 和 T。
以下 M 行每行包含两个整数 ts 和 id,表示 ts 时刻编号 id 的外卖店收到
一个订单。
【输出格式】
输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

【样例输出】
1
【样例解释】
6 时刻时, 1 号店优先级降到 3,被移除出优先缓存; 2 号店优先级升到 6,
加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。
【评测用例规模与约定】
对于 80% 的评测用例, 1 ≤ N; M; T ≤ 10000。
对于所有评测用例, 1 ≤ N; M; T ≤ 100000, 1 ≤ ts ≤ T, 1 ≤ id ≤ N。

题解: 由题意可知缓存条件是优先级大于5,而被清除的缓存的条件是优先级小于等于3, 第一次做这个题, 我就把他搞错了.
使用集合存放每个时间有过订单的外卖店.需要注意的是不能用Set集合,因为同一个时间同一个外卖店可能有多个订单.
具体请看代码.

package ten;
 
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class 外卖店优先级{
 
    public static void main(String[] args)  {
     Scanner shu = new Scanner(System.in);
     int N=shu.nextInt();
     int M=shu.nextInt();
     int T=shu.nextInt();
     int yxj[]=new int[N+1];//优先级
     int count=0;
     int hc[]=new int [N+1];//缓存 没有缓存为0 有缓存为1
     List [] time=new ArrayList[T+1]; //每个时间有订单的外卖店
     for(int i=0;i<=T;i++)
    	 time[i]=new ArrayList();//每个时间可能有多个外卖店有订单产生
     for(int i=1;i<=M;i++) {
    	 int ts=shu.nextInt();
    	 int id=shu.nextInt();
    	 time[ts].add(id);//每个时间产生的外卖店
     }
     for(int i=1;i<=T;i++) {//枚举每个时间的外卖店
    	 for(int j=1;j<=N;j++) {//枚举外卖店
    		 int flag=0;
    		 Object k=j;
    		 while(time[i].contains(k)) {//同一个时间同一个外卖店可能存在多个订单
    			 flag=1;//有订单标记为1
    			 time[i].remove(k);
    			 yxj[j]+=2;
    			 if(yxj[j]>5) {
    				 count++;    				 
    				 hc[j]=1;
    			 }
    		 }
    		 if(flag==0) {//无订单
    			 yxj[j]=yxj[j]==0?0:yxj[j]-1;
    			 if(hc[j]==1&&yxj[j]<=3) {//已在缓存且优先级小于等于3
    				 hc[j]=0;//清除缓存
    				 count--;
    				 }
    			 }
    		 }
    	 }
     System.out.println(count);
    }
 
}

分享到:
赞(0) 打赏

评论 5

评论前必须登录!

 

  1. #1

    奥利给

    白云6个月前 (03-27)
  2. #2

    我也是小白以后多多交流

    你好6个月前 (03-28)
  3. #3

    挺明白的

    小白4个月前 (05-26)
  4. #4

    看了那么多博客,就你的能看懂

    你哥4个月前 (05-26)
  5. #5

    看了那么多博客,就你的能看懂

    沥青4个月前 (05-26)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00