[蓝桥杯2019初赛]外卖店优先级（模拟）C++

问题 F: [蓝桥杯2019初赛]外卖店优先级 - BUCTOJ

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

输出：

输出一个整数代表答案。

分析

一开始我上来就直接模拟，想法是存储每个店铺的接到订单的时间，然后遍历店铺，模拟每家店铺在时间t内优先度的变化，这样一来时间复杂度为O(T*N)，更要命的是怎么存储这个时间呢，我本来想开个二维数组（这样还要离散化），但一看数据范围直接爆掉了，就用map吧，将记录时间的容器映射到店铺上面，就有了这个奇怪的东西(bushi，map>，根据我的经验，map中要用到第二种容器的都过不了，用这个奇怪的东西时间复杂度都不懂高到哪里去了，于是果不其然TLE了。

#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
map> od;
int main()
{
    int n, m, t;
    cin >> n >> m >> t;
    for (int i = 0; i < m; i++)
    {
        int ts, id;
        cin >> ts >> id;
        od[id].insert(ts);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        multiset thisshop = od[i];
        int pr = 0;
        bool in = false;
        for (int j = 1; j <= t; j++)
        {
            if (thisshop.find(j) != thisshop.end())
            {
                pr += 2 * thisshop.count(j);
                if (pr > 5)
                {
                    in = true;
                }
            }
            else
            {
                pr = max(0, pr - 1);
            }
        }
        // cout << "priority of shop " << i << " " << pr << endl;
        if (pr <= 3)
            in = false;
        if (in)
            ans++;
    }
    cout << ans;
    return 0;
}

能不能在读取那m条信息时就处理好呢，排个序就好，那就看正解吧：

为了将记录店铺和时间的信息关联起来，我开了一个pair数组来存储，这里先说一声，对它排序时是默认按照first的大小来排的，这样就按照时间的顺序排序（时间是重要的，不考虑时间的间隔妄图直接得到答案是不可能的）。

大概思路就是在处理信息的时候同时处理店铺的优先级，开了一个优先级数组pr，一个数组last（后面再说干什么用的），一个布尔数组判断店铺是否在优先缓存中。我们遍历pair数组时每遇到一个店铺（no=pi[i].second),就将其优先级加2，但那些因为在没有订单的时间减小的优先级怎么计算呢，这里有多个店铺的信息啊，就需要一个last来记录该店铺上一次有订单的时间，处理时用这次时间（pi[i].first)减去上一次时间即可（这里别忘了减一，时间嘛）。还有一个点就是题目说大于5才加入优先缓存但小于等于3才出缓存，那处于4和5之间的优先值怎么知道这个店铺在不在优先缓存中呢，就需要在这个过程中同时处理这一点，如果优先值大于5，in标记为true。

最后再遍历店铺，这时还要减去处于尾部的时间造成的优先值损失，last数组又派上用场，再次判断是否满足优先缓存，更新ans。

AC代码

#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
pair pi[N];
int pr[N], last[N];
bool in[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, t;
    cin >> n >> m >> t;

    for (int i = 0; i < m; i++)
    {
        cin >> pi[i].first >> pi[i].second;
    }
    sort(pi, pi + m);
    for (int i = 0; i < m; i++)
    {
        int no = pi[i].second;
        pr[no] += 2;
        if (last[no]) //如果是首次出现优先值是0前面也没有优先级损失
            pr[no] -= (pi[i].first - last[no] - 1);
        pr[no] = max(pr[no], 0); //注意优先级是非负的
        if (pr[no] > 5) //在线判断
        {
            in[no] = true;
        }
        // cout << no << " priority is:  " << pr[no] << endl;
        last[no] = pi[i].first; //更新last
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        pr[i] -= (t - last[i]);
        // cout << "left: " << pr[i] << endl;
        if (pr[i] <= 3) //判断减去最后一段损失后的情况
            in[i] = false;
        else if (pr[i] > 5)
            in[i] = true;
        if (in[i])
            ans++;
    }
    cout << ans;
    return 0;
}

时间复杂度:O(nlogn) -排序