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

飞熊 • 2023年4月9日下午9:18 • 技术随笔 • 阅读 217

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

The Right Path – Thomas Greenberg

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

但是至少是明白了

😎😎😎😎😎😎

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

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

下面就是优化版本

⭐⭐⭐

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

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

具体可以参考下面的代码

⭐⭐⭐

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

#include <iostream>
#include <algorithm>

#define x first
#define y second

using 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 id
    sort(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）

🍔最后一个订单怎么处理