2021年寒假每日一題，2017~2019年的省賽真題，本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，每日一題，關注藍橋杯專欄: https://blog.csdn.net/weixin_43914593/category_10721247.html

每題提供C++、Java、Python三種語言的代碼，

2019省賽A組第7題“外賣店優先級” ，題目鏈接：
http://oj.ecustacm.cn/problem.php?id=1458
https://www.dotcpp.com/oj/problem2300.html

1、題目描述

“飽了么”外賣系統中維護著N 家外賣店，編號1~N，
每家外賣店都有一個優先級，初始時(0 時刻) 優先級都為0，
每經過1 個時間單位，如果外賣店沒有訂單，則優先級會減少1，最低減到0；
而如果外賣店有訂單，則優先級不減反加，每有一單優先級加2，
如果某家外賣店某時刻優先級大于5，則會被系統加入優先快取中；
如果優先級小于等于3，則會被清除出優先快取，
給定T 時刻以內的M 條訂單資訊，請你計算T 時刻時有多少外賣店在優先快取中，
輸入：第一行包含3 個整數N、M 和T，
以下M 行每行包含兩個整數ts 和id，表示ts 時刻編號id 的外賣店收到一個訂單
1<=N, M, T<=100000，1<=ts<=T，1<=id<=N，
**輸出：**輸出一個整數代表答案，

2、題解

??模擬題，純粹的模擬，
??無話，

3、C++代碼

//改寫自：https://www.jianshu.com/p/1e625af51a3a
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

int order[N];  //order[id]  第id號店上一次的訂單
int prior[N];  //prior[id]  第id號店的優先級
int flag[N];   //flag[id]   第id號店在不在優先快取中

struct node{
    int time,id;
}a[N];

bool cmp(node a, node b){
    if(a.id==b.id)
        return a.time<b.time;
    return a.id<b.id;
}

int main(){
    int m,n,T;  cin>>n>>m>>T;
    for(int i=0;i<m;i++)
        cin>>a[i].time>>a[i].id;
    sort(a,a+m,cmp); //按時間排序
    for(int i=0;i<m;i++){
        int tt=a[i].time,  id=a[i].id;
        if(tt != order[id])  //如果當前訂單不等于上一次的訂單，則減去它們之間的間隔
            prior[id] -= tt-order[id]-1;
        prior[id] = prior[id] < 0 ? 0: prior[id];  //不小于0
        if(prior[id]<=3)  flag[id]=0;
        prior[id]+=2;
        if(prior[id]> 5)  flag[id]=1;
        order[id]=tt;
    }
    for(int i=1;i<=n;i++)  //最后處理第T時刻
        if(order[i]<T){
            prior[i] -= T-order[i];
            if(prior[i]<=3)
                flag[i]=0;
        }

    int ans=0;
    for(int i=0;i<=n;i++)
        if(flag[i])
            ans++;
    cout<<ans;
    return 0;
}

4、Python代碼

?? 把上面的C++代碼改寫成Python：

first = input()
n, m, T = [int(i) for i in first.split()]
a = []
 
priorty = []
for i in range(m):
    a.append([int(i) for i in input().split()])
a = sorted(a, key=lambda a: a[0])

order=[]  
prior=[]
flag=[]
order = [0 for i in range(n+1)]
prior = [0 for i in range(n+1)]
flag = [0 for i in range(n+1)]

for i in range(m):
    tt = a[i][0]     #time
    idd = a[i][1]    #id
    if tt != order[idd]:
         prior[idd] -= tt-order[idd]-1
    if prior[idd] < 0:   prior[idd] =0
    if(prior[idd]<=3):   flag[idd]=0
    prior[idd] += 2;
    if(prior[idd]> 5):   flag[idd]=1
    order[idd]=tt
for i in range (1,n+1):
    if(order[i]<T):
        prior[i] -= T-order[i]
        if(prior[i]<=3): flag[i]=0
ans=0
for i in range(n+1):
    if(flag[i]>0):
        ans +=1
print(ans)

5、Java代碼

//http://oj.ecustacm.cn/ User: 181549228
import java.util.ArrayList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;
  
public class Main {
    static Scanner in = new Scanner(System.in);
    static int n, m, t;
    static Map<Integer, ArrayList<Integer>> map = new TreeMap<Integer, ArrayList<Integer>>();
    static int result;
  
    public static void main(String[] args) {
        n = in.nextInt();
        m = in.nextInt();
        t = in.nextInt();
        for (int i = 1; i <= m; ++i) {
            int time = in.nextInt();
            int id = in.nextInt();
            if (map.containsKey(id)) {
                map.get(id).add(time);
            } else {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(time);
                map.put(id, temp);
            }
        }
  
        ArrayList<Map.Entry<Integer, ArrayList<Integer>>> list = new ArrayList<Map.Entry<Integer, ArrayList<Integer>>>(
                map.entrySet());
        for (int i = 0; i < list.size(); ++i) {
            Entry<Integer, ArrayList<Integer>> entry = list.get(i);
            ArrayList<Integer> list2 = entry.getValue();
            int num = 0;
            int[] count = new int[t + 2];
            boolean flag = false;
            for (int j = 0; j < list2.size(); ++j)
                count[list2.get(j)]++;
  
            for (int j = 1; j <= t; ++j) {
                if (count[j] == 0) {
                    if (num > 0)
                        num--;
                    if (num <= 3)
                        flag = false;
                } else {
                    num += count[j] * 2;
                    if (num > 5)
                        flag = true;
                }
            }
            if (flag)
                result++;
        }
        System.out.println(result);
    }
}