【蓝桥杯】外卖店优先级题解

- 日理万妓 2023-07-09 02:29 2阅读 0赞

> 【问题描述】
> 
> “饱了么”外卖系统中维护着 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

## 分析 ##

题目应该比较好读懂,需要注意一下几点

*  店铺加入优先缓存中还会增加优先级
 *  店铺只有先加入后才能有移除这一说

**数据结构**

*  存储优先级的数组
 *  优先缓存区队列
 *  记录每一时刻的订单情况的数据结构,考虑到时间和商家是1对多的关系,使用hashmap<Integer,ArrayList<Integer > >组合的方式

**收获**

*  在多个判断条件组合的情况下,很不容易弄清楚if-else的层次,不如将条件分开,而不用逻辑连接起来,这样可能更容易明白
 *  如果只用考虑单个的几种情况,而每种情况之间是独立但不是仅仅的互斥关系,可以写成函数每个if语句里加上return,这样就不用考虑else的这种互斥面

## 参考代码 ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Scanner;
    
    class Main { 
    	static int n, m, t, value[];
    	static Queue<Integer> buffer = new LinkedList<Integer>();
    	static HashMap<Integer, ArrayList<Integer>> hp = new HashMap<Integer, ArrayList<Integer>>();
    
    	public static void judeg(int i) { 
    		if (value[i] > 5 && !buffer.contains(i)) { 
    			buffer.offer(i);
    			return;
    		}
    		if (value[i] <= 3 && buffer.contains(i)) { 
    			buffer.remove(i);
    			return;
    		}
    	}
    
    	public static void main(String[] args) { 
    		Scanner scanner = new Scanner(System.in);
    		n = scanner.nextInt();
    		m = scanner.nextInt();
    		t = scanner.nextInt();
    		int ts, id;
    		value = new int[n + 1];
    		for (int i = 0; i < m; i++) { 
    			ts = scanner.nextInt();
    			id = scanner.nextInt();
    			if (hp.containsKey(ts))
    				hp.get(ts).add(id);
    			else { 
    				ArrayList<Integer> a = new ArrayList<Integer>();
    				a.add(id);
    				hp.put(ts, a);
    			}
    		}
    		for (int i = 1; i <= n; i++) { 
    			for (int j = 1; j < t; j++) { 
    				ArrayList<Integer> a = hp.get(j);
    				if (a != null && a.contains(i)) { 
    					for (int x : a) { 
    						if (x == i) { 
    							value[i] += 2;
    							judeg(i);
    
    						}
    					}
    				} else { 
    					value[i]--;
    					judeg(i);
    				}
    			}
    		}
    		System.out.println(buffer.size());
    	}
    }