【AcWing】学了一坤时才明白的一道题

🎆音乐分享 （点击链接可以听哦）

The Right Path - Thomas Greenberg
 

---

 

这道题小吉花了一坤时才弄明白，虽然花的时间有点长

但是至少是明白了

😎😎😎😎😎😎 

1241. 外卖店优先级 - AcWing题库 

 

这道题如果纯纯用暴力，也不是不能做，毕竟是蓝桥杯的题，还是可以拿到分的，但是拿不全

下面就是优化版本

⭐⭐⭐

注意用sort为pair排序时，先比较  .first，再比较  .second,

变化位置时，  .first  .second 一起变化

具体可以参考下面的代码

⭐⭐⭐

代码的总体思路就是先排序，把 ts 相同的放在一起 

#include <iostream>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 100010;int n, m, T;
int score[N];//优先级
int last[N];//店铺i上一次有订单的时间 
bool st[N];//是否加入到优先缓存中PII order[N];int main()
{scanf("%d%d%d", &n, &m, &T);for (int i = 0; i < m; i ++ ) scanf("%d%d", &order[i].x, &order[i].y);// ts idsort(order, order + m);for (int i = 0; i < m;){int j = i;while (j < m && order[j] == order[i]) j ++ ;//代表order[].x order[].y都对应相等int t = order[i].x, id = order[i].y, cnt = j - i;i = j;score[id] -= t - last[id] - 1;//时间差，具体看下面的解释if (score[id] < 0) score[id] = 0;if (score[id] <= 3) st[id] = false; // 以上处理的是t时刻之前的信息score[id] += cnt * 2;if (score[id] > 5) st[id] = true;last[id] = 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 ++ ) res += st[i];printf("%d\n", res);return 0;
}

 🍔 score[id] - = t - last[id] - 1

t 代表当前时间，last[id]代表 t 前一个的时间，因为要算出整块的时间，这样方便改变优先值

因为已经跳出while循环了，所以这一部分是没有接到订单的，所以是score[] -  

为什么要 -1

比如 t = 5,last[id] = 2,那么就是 3，4两个数（5-2-1）

🍔最后一个订单怎么处理

 Code over！