蓝桥杯:外卖店优先级(map排序算法) Java

分析:

• 发现只是输入两种数据,则可以考虑用map
• 经过分析发现,可以用店家编号来表示map的第一个参数Integer,第二个参数因为有可能有多个相同的时刻,所以用arraylist<Integer>
• 然后遍历每一家店,判断是不是在优先缓存中
• 利用count[]录入输入时刻的订单,最后遍历每个时刻来判断

进步:

• treemap的key不可重复,但是treemap的key可以自动升序排列
• if(map.containsKey(id)){}
• 如果第二个参数是arraylist,则可map.get(id).add(t)
• list.add()
• map.put()
• for(Integer key:map.keyset())
• 利用count[]的下标来表示时刻,值来表示多少个订单数(可以发现他和map有点像,但是和map的差距是,没有containsKey()等方法,唯一的好处是比较简单)
• 利用flag来判断是否在优先缓存中
• 一定要注意好,题目到底让你输出什么,根据你要输出什么来写出逻辑

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Map;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int nd=scan.nextInt();//店数量
        int n=scan.nextInt();//几条订单信息
        int t=scan.nextInt();//多少个时刻
        //参数1表示店id,参数2表示有多少个时刻
        Map<Integer,ArrayList<Integer>> map=new TreeMap<>();

        for(int i=0;i<n;i++){
            int time=scan.nextInt();
            int id=scan.nextInt();
            if(map.containsKey(id)){
                map.get(id).add(time);
            }else{
                ArrayList<Integer> temp=new ArrayList<Integer>();
                temp.add(time);
                map.put(id, temp);
            }
        }
        int result=0;//统计有多少家店在优先缓存中

        //遍历每一家店
        for (Integer key: map.keySet()) {
            int[] count=new int[t+1];//表示某个时刻收到多少订单

            //遍历arraylist,赋值订单
            ArrayList<Integer> list=map.get(key);
            for(int i=0;i<list.size();i++){
                //输入时刻的订单录入
                count[list.get(i)]+=1;
            }

            int priority=0;//优先级
            boolean flag=false;//显示这家店是否还在优先缓存
            //遍历每个时刻
            for(int i=1;i < count.length;i++){
                //如果有订单,优先级加2
                if(count[i]!=0){
                    priority+=count[i]*2;
                    if(priority>5){
                        flag=true;
                    }
                }else{
                    //如果没有订单,则优先级-1
                    //如果优先级
                    if(priority!=0){
                        priority--;
                    }                        
                    if(priority<=3){
                            flag=false;
                    }
                }
            }

            if(flag==true){
                result++;
            }
        }

        System.out.println(result);
        scan.close();
    }
}