【蓝桥】外卖店优先级

题目

题目描述

“饱了么”外卖系统中维护着 NN 家外卖店,编号 1 ∼ N。每家外卖店都有 一个优先级,初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位,如果外卖店没有订单,则优先级会减少 1,最低减 到 0;而如果外卖店有订单,则优先级不减反加,每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5,则会被系统加入优先缓存中;如果 优先级小于等于 3,则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息,请你计算 T 时刻时有多少外卖店在优 先缓存中?

输入描述

第一行包含 3 个整数 N,M,T。

以下 M 行每行包含两个整数 ts,id ,表示 tsts 时刻编号 id 的外卖店收到一个订单。

其中,1 ≤ N, M ,T≤10^5,1≤ts≤T, 1≤id≤N。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

1
2
3
4
5
6
7
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出

1
1

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

解题

源码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//改写自: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;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
first = input()
n,m,T=[int (i) for i in first.split()]
a=[]

for i in range(m):
a.append([int(i) for i in input().split()])

#对订单的的时间进行排序,目的是算出当前订单与上一回订单之间的间隔
#从未计算出这家店没有订单的时候优先级下降数
#即:prior[idd] -= tt-order[idd]-1
a=sorted(a,key=lambda a:a[0])

order=[]#订单的时刻
prior=[]#优先级的分数
flag=[]#是否在优先缓存中
#初始化为0
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]
idd=a[i][1]
#如果当前订单的时间不等于上次的订单
#由题意每过一秒优先级减1,所以优先级减去间隔
if tt != order[idd]:
prior[idd] -= tt-order[idd]-1
if prior[idd]<0: prior[idd]=0#优先级最低为0
if prior[idd]<=3: flag[idd]=0
prior[idd]+=2 #有订单则优先级加2
if prior[idd]>5: flag[idd]=1
order[idd]=tt #记录这次订单的时间,下此迭代使用

#处理到了T时刻的情况
for i in range(1,n+1):
#如果最后一个订单不是T时刻的
#要减去最后一趟订单时间与t的差的绝对值
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)

总结

C++版

  1. 标准答案,但是我口算一直觉得有问题啊,因为一共就6条记录,口算根本不满足优先级是5以上的条件,怎么会有一个店铺被加入到优先级缓存?

Python版

  1. 二维数组,方法逻辑一样的