蓝桥杯外卖店优先级

以你之姓@ 2023-03-13 06:55 3阅读 0赞

### 这里写自定义目录标题 ###

*  题目：
 *  暴力分析（80%）：
 *  80%代码：
 *  满分分析：
 *   *  在内存上的优化：
     *  在运行上的优化：
     *  有个坑：
 *  AC代码：

# 题目： #

[外卖店优先级][Link 1].  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]  
先来一张AC图片  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]

# 暴力分析（80%）： #

直接模拟运算过程，  
创建一个二维数组，横坐标为店的 id，纵坐标为时间 ti，  
每获取一个订单，就在（id，ti）的位置+1；  
最后遍历一下二维数组即可。  
时间复杂度O(n\*t）

# 80%代码： #

package JC2019;
    
    //正确
    import java.util.Scanner;
    
    /*试题 G: 外卖店优先级 时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分 * */
    public class G暴力 { 
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt(), m = sc.nextInt(), t = sc.nextInt();
    
    		int arr[][] = new int[t + 1][n + 1];
    
    		for (int i = 0; i < m; i++) { 
    			arr[sc.nextInt()][sc.nextInt()]++;
    		}
    		int prio[] = new int[n + 1];
    
    		for (int i = 1; i < t + 1; i++) { 
    			for (int j = 1; j < n + 1; j++) { 
    				if (arr[i][j] > 0) { 
    					arr[i][j] = arr[i - 1][j] + arr[i][j] * 2;
    					if (arr[i][j] > 5)
    						prio[j] = 1;
    				} else { 
    					if (arr[i - 1][j] > 0) { 
    						arr[i][j] = arr[i - 1][j] - 1;
    						if (arr[i][j] < 4)
    							prio[j] = 0;
    					}
    				}
    			}
    		}
    		int ans = 0;
    		for (int i = 0; i < prio.length; i++) { 
    			ans += prio[i];
    		}
    		System.out.println(ans);
    	}
    }

# 满分分析： #

## 在内存上的优化： ##

矩阵存储时会有大量空间被浪费。  
所以采用一维数组的Map存储，key存储id，value存储订单次数。

## 在运行上的优化： ##

很多对店铺优先级的-1操作，  
所以我们可以在纵向考虑区间操作。  
记录下每个店铺最后一次接受订单的时间，  
每当接收到一个订单，我们才对他进行减少优先级和增加优先级的操作。  
最终接受完所有订单后，再对所有店铺进行一次减少优先级操作。

## 有个坑： ##

虽然优先级的减少和增加貌似是一起进行的，但是，容易出现一种特殊情况。  
店家本来优先级为6…就是说店家在优先级内  
如果第四天接到1个订单…店家此时优先级为4，但是不在优先队列内。  
所以优先级的减少和增加应该分开操作，并且每次操作后都应该进行判断，此时是否应该存在于优先队列

# AC代码： #

package JC2019;
    
    import java.util.*;
    
    public class Main { 
    	public static void main(String[] args) { 
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		int m=sc.nextInt();
    		int t=sc.nextInt();
    		HashMap<Integer,Integer> arr[]=new HashMap[t+1];
    		for(int i=0;i<t+1;i++){ 
    			arr[i]=new HashMap<Integer,Integer>();
    		}
    		int id,ti;
    		for(int i=0;i<m;i++){ 
    			ti=sc.nextInt();
    			id=sc.nextInt();
    			if(arr[ti].containsKey(id)){ 
    				arr[ti].put(id, arr[ti].get(id)+1);
    			}else{ 
    				arr[ti].put(id, 1);
    			}
    		}
    		int last[]=new int[n+1];
    		int scor[]=new int[n+1];
    		int prio[]=new int[n+1];
    		for(int i=0;i<=t;i++){ 
    			for(int temp:arr[i].keySet()){ 
    				scor[temp]=Math.max(scor[temp]-(i-last[temp]-1),0);
    				if(scor[temp]>5&&prio[temp]==0){ 
    					prio[temp]=1;
    				}else if(scor[temp]<4&&prio[temp]==1){ 
    					prio[temp]=0;
    				}
    				scor[temp]+=arr[i].get(temp)*2;
    				if(scor[temp]>5&&prio[temp]==0){ 
    					prio[temp]=1;
    				}
    				last[temp]=i;
    			}
    		}
    		for(int i=0;i<=n;i++){ 
    			scor[i]=Math.max(scor[i]-(t-last[i]),0);
    			if(scor[i]<4&&prio[i]==1){ 
    				prio[i]=0;
    			}
    		}
    		int ans=0;
    		for(int i=0;i<=n;i++){ 
    			ans+=prio[i];
    		}
    		System.out.println(ans);
    	}
    }

[Link 1]: https://www.acwing.com/problem/content/1243/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230312/bb03a1413a66449f83bb8412dbf49ad1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200512172513541.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200512172532964.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200512175317547.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3,size_16,color_FFFFFF,t_70