外卖店优先级问题（双指针降低时间复杂度）

外卖店优先级问题

问题详情

“饱了么”外卖系统中维护着 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≤105
1≤ts≤T
1≤id≤N

输入样例：
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出样例：
1
样例解释
6
时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。

所以是有 1 家店 (2 号) 在优先缓存中。

问题分析

1、普通思路

时间复杂度O（n^2）,会超时

1、1输入储存问题

由题意分析，我们最后取 t 时刻的优先队列状态，自然需要对之前输入的数据进行排序，按字典序正序排列进行存储

for(int i=1;i<=m;i++) {
        int ts,id;
        cin>>ts>>id;
        order[i]={ts,id};
    }
    sort(order+1,order+1+m);
1
2
3
4
5
6

这里直接放出代码，至于排序一般都是按照字典序来的，直接使用sort函数即可，如果各位觉得不保险的话可以使用结构体的自定义排序手法

struct Edge{
    int a,b;
    bool operator <(const Edge &W) const
    {
        if(a==W.a) return b<W.b;
        else return a<W.a;
    }
}edges[N];
1
2
3
4
5
6
7
8

1、2 遍历存储的数据

这里我们就需要 数组 f [ N ],来记录每个 id 的优先级，数组 s t [ N ] 来设置优先队列当中存储了哪些 id ;数组 used [ N ] 记录哪些时间点没被重复使用
每次拿出一个数据进行分析，对该时刻的 id 对应的优先级 +=2，其他 id -1操作，这里的时间复杂度是O(N * N)

1、3遍历 st [ N ] 数组，获得最终值

总结下来思路简单，代码实现也不难，但是会超时，所以有没有更好的方法呢？

2、双指针【时间复杂度 O( n )】

和上面的思路部分一致
需要 数组 f [ N ],来记录每个 id 的优先级
数组 s t [ N ] 来设置优先队列当中存储了哪些 id
还需要数组 last [ N ]记录该 id 上一次更新的时间【这一步简化了修改每一个时间点每一个ID对应的优先级过程】

代码【具体的解析都在注释当中，其中困惑的点都会距离说明】

#include
#include
using namespace std;
const int N =1e5 + 7;
int f[N],last[N];
bool st[N];
int n,m,T;
typedef pair<int,int> PII;
PII order[N];
int main(){
    cin>>n>>m>>T;
    for(int i=1;i<=m;i++) {
        int ts,id;
        cin>>ts>>id;
        order[i]={ts,id};
    }
    sort(order+1,order+1+m);
    //输入的起始下标是 1 ，所以排序的时候要改成 1 开始
    for(int i=1;i<=m;){//这里就是双指针操作， i 的增长会在循环中实现
        int j=i;
        while(order[i]==order[j] && j<=m) j++;
        //为什么这里的 j 可以<=m 呢？
        // 注意下面的 j-i ，这里代表的是更新到某 id 时应该增加“+=2”的次数
        //同时这里还考虑到了多次在相同 id 上面下单的情况
        int t=order[i].first,id=order[i].second,cnt=j-i;
        i=j;//这里对i进行更新维护，注意不要和上面那一行代码顺序搞反了！！！！
        f[id]-=t-last[id]-1;//这里举个例子大家就很容易理解了
    	//假设上次更新的时间是 3s ，这次更新的时间是 5s,
    	//那么在 3~5s 的时间里，我们减少了 5- 3 -1 的优先级
    	//为什么要减 1 呢？
    	//因为要把 5s 排除在外，【减去的数值应当是没有处于更新状态下的时间段！！！】
        if(f[id]<0) f[id]=0;
        //开始更新维护 f [ N ]，防止其储存负数
        if(f[id]<=3) st[id]=false;
        f[id]+=cnt*2;
        if(f[id]>5) st[id]=true;
        last[id]=t;//更新上次更新的时间为此次 t 
    }
    int res=0;
    //下面是对 T 时刻的遍历，遍历对象是每个 ID
    for(int i=1;i<=n;i++){
        if(last[i]<T){
            f[i]-=T-last[i];//这里我们的更新为什么没有 - 1 操作呢 ？
            //我们再举个例子就知道了
			//假设最终时间是 T =5 ，上次更新时间是 t = 3s;
			//并且我们在第 5 秒的时候没有进行更新，不用将 第 5 秒排除在外
			//所及计算结果是 f[ i ] -= 5 - 3 ;
            if(f[i]<=3) st[i]=false;
        }
    }
    for(int i=1;i<=n;i++) res+=st[i];//计算出最终结果
    cout<<res<<endl;
}
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
53