第十届蓝桥杯javaB组 G题：外面优先级（java实现）

Love The Way You Lie 2023-06-24 06:23 35阅读 0赞

试题 G: 外卖店优先级
    时间限制: 1.0s 内存限制: 512.0MB 本题总分： 20 分
    【问题描述】
    “饱了么”外卖系统中维护着 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

此解决方案为一般方法会出现算法复杂度过高，导致部分用例超时，也是网上搜索到大部分写法。

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
    	static int[] shop=new int[100005];
    	static boolean[] isStore=new boolean[100005];
    	static ArrayList<Integer>[] timeList;
    	public static void main(String[] args) {
    		Scanner cin=new Scanner(System.in);
    		int n=cin.nextInt();
    		int m=cin.nextInt();
    		int t=cin.nextInt();
    		timeList=new ArrayList[t+1];
    		for(int i=1;i<=t;i++) {
    			timeList[i]=new ArrayList<Integer>();
    		}
    		for(int i=1;i<=m;i++) {
    			int time=cin.nextInt();
    			int id=cin.nextInt();
    			timeList[time].add(id);
    		}
    		way1(n);
    		int number=0;
    		for(boolean is:isStore) {
    			if(is) {
    				number++;
    			}
    		}
    		System.out.println(number);
    	}
    	
    	//时间复杂度达到10次方必定超时  复杂的原因是内层循环嵌套了一个检查数组中的每个数是否大于0
    	public static void way1(int n) {
    		
    		for(int j=1;j<=timeList.length-1;j++) { //时间复杂度5次方
    			ArrayList<Integer> a=timeList[j];
    			if(a.size()!=0) {
    				for(int shopId:a) {
    					shop[shopId]+=3;
    					if(shop[shopId]-1>5) {
    						isStore[shopId]=true;
    					}
    				}
    			}
    			//时间复杂度5次方
    			for(int i=1;i<=n;i++) {
    				if(shop[i]>0) {
    					shop[i]-=1;
    					if(shop[i]<=3) {
    						isStore[i]=false;
    					}
    				}
    			}
    		}
    	}
    	
    }

此解决方法不会出现用例超时现象

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    
    public class Main {
        static int  N=100005;
        //score 数组记录每个店铺得分
        static int[] score=new int[N];
        //last数组 是每个店铺最后一次接收到订单的时刻
        static int[] last=new int[N];
        //st数组记录是否进入优先缓存区
        static boolean[] st=new boolean[N];
        static ArrayList<Order> list=new ArrayList<Order>();
        public static void main(String[] args) {
            Scanner cin=new Scanner(System.in);
            int n=cin.nextInt();
            int m=cin.nextInt();
            int t=cin.nextInt();
            for(int i=0;i<m;i++) {
                int ts=cin.nextInt();
                int id=cin.nextInt();
                list.add(new Order(ts,id));
            }
            Collections.sort(list);
            for(int i=0;i<m;i++) {
                int j=i;
                Order a =list.get(i);
                int time=a.time; int id=a.id;
                //记录同一时刻，相同id的店铺一共接受j个订单
                while(list.get(j).time==time&&list.get(j).id==id) {
                    j++;
                    if(j==list.size()) {
                        break;
                    }
                }
                //优先级得分要减去 当前店铺在之前最后一次接收订单的时间和当前时刻再次接收到订单的时间差
                score[id]-=time-last[id]-1;
                if(score[id]<0) score[id]=0;
                if(score[id]<=3) st[id]=false;
                last[id]=time;
                //优先级得分要加上 当前时刻 接收到的总订单数(j-i)*2
                score[id]+=(j-i)*2;
                if(score[id]>5) {
                    st[id]=true;
                }
                //i下次是从j的位置开始遍历，因为i到j都是同样的id和time，但是要减1，因为执行完了循环体++1
                i=j-1;
            }
    
            for(int i=1;i<=n;i++) {
                if(last[i]<t) {
                    score[i]-=t-last[i];
                    if(score[i]<0) score[i]=0;
                    if(score[i]<=3) st[i]=false;
                }
            }
    
            int res=0;
            for(int i=1;i<=n;i++) {
                if(st[i]==true) res++;
            }
            System.out.println(res);
        }
    }
    
    
    class Order implements Comparable<Order>{
    
        int time;
        int id;
    
        public Order(int time, int id) {
            super();
            this.time = time;
            this.id = id;
        }
        @Override
        public int compareTo(Order o) {
            // TODO Auto-generated method stub
            if(this.time==o.time) {
                return this.id-o.id;
            }
            return this.time-o.time;
        }
        @Override
        public String toString() {
            return "Order [time=" + time + ", id=" + id + "]";
        }
    }