外卖店优先级c++

题目

输入样例：

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

输出样例：

1

样例解释

6时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。

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

思路

首先说一下暴力做法。我们可以用pair<int, int>来存订单信息，然后按时刻对其进行排序。从前往后遍历一遍订单信息，对于每个时刻，有订单的外卖店优先级加2，无订单的外卖店优先级减1。最后判断哪些外卖店优先级大于5。伪代码如下：

pair<int, int> record[N];//记录外卖信息
int a[N];//a[i]表示第i家外卖店的优先级

sort(record, record + M);

for (i: 0 -> M)
{
    for (i:0 -> M)
    {
        //判断哪些加优先级，哪些减优先级
    }
}

for (i: 0 -> N)//判断哪些优先级大于5

可以看到时间复杂度为O(10^10)，可以尝试优化“改变优先级”这部分操作。

我们可以在遍历record数组的过程中使用一个last数组记录一家外卖店上一次接到订单的时间，等到该外卖店的订单再次出现时再处理没有订单期间带来的优先级减少；而不是每一时刻都把没有订单的店铺的优先级减1。如果在同一时刻一家店铺有多个订单，那么就批量处理。

以前的思路是针对一个订单信息的时刻，一个时刻处理所有店铺的优先级，而现在的思路是针对一个订单信息的店铺，一家店铺处理一家店铺的优先级。

代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;

PII record[N];
int last[N], score[N];//last[i]表示编号为i的店铺最后一次订单在什么时刻；score[i]表示店铺当前的优先级
bool st[N];//st[i]表示编号为i的店铺是否在缓存中

int main()
{
  int n, m, t;
  
  scanf("%d%d%d", &n, &m, &t);
  
  for (int i = 0; i < m; i ++)
  {
    int ts, id;
    scanf("%d%d", &ts, &id);
    record[i] = {ts, id};
  }
  
  sort(record, record + m);
  
  for (int i = 0; i < m;)
  {
    int ts = record[i].x, id = record[i].y;
    /*
    处理ts时刻之前外卖店铺编号为id减少的优先级
    不可能出现last[id] = ts - 1的情况；因为while循环对于连续时间内同Id的订单已经做了处理
    */
    score[id] -= (ts - last[id] - 1);
    if (score[id] <= 3) st[id] = false;
    if (score[id] < 0) score[id] = 0;
    
    /*
    处理外卖店铺编号为id在ts时刻及以后的连续时刻增加的优先级
    */
    while (id == record[i].y && i <= m)
    {
      score[id] += 2;
      last[id] = record[i].x;
      if (score[id] > 5) st[id] = true;
      i ++;
    }
  }
  
  //处理每家店铺的最后一个订单时刻到T时刻减少的优先级
  for (int i = 1; i <= n; i ++)
  {
    if (last[i] < t)
    {
      score[i] -= (t - last[i]);
      if (score[i] <= 3) st[i] = false;
    }
  }
  
  
  int res = 0;
  for (int i = 1; i <= n; i ++)
  if (st[i])res ++;
  
  printf("%d", res);
  return 0;
}