外卖店优先级

题目

题目链接

分析

拿到题目之后，首先想想暴力的做法，暴力的做法按照时间枚举，在某个时间点上枚举所有的外卖店若是有订单优先级就加上cnt(订单的数量) * 2，否则就减去1，再按照优先级的数值判断是否在优先缓存中。枚举完所有时间以后，再看T时刻的优先缓存中的外卖店的数量。这种暴力的时间复杂度我写的代码是，显然是会超时的。

然后再想怎么优化，再按照时间枚举的过程中，其实对于某个店铺来说在很多时间上是没有订单的，比如说t1到t2时刻中i店铺没有订单，则t2时刻的优先级应该为：max(0, score[i] - (t2 - t1 - 1)) + 2，这样就避免了枚举中间没有订单的时间点。

C++代码

暴力枚举

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 100010;

int n, m, T;

PII orders[N];
int score[N];
bool st[N];
bool f[N];

int main()
{
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < m; i++) scanf("%d%d", &orders[i].x, &orders[i].y);
    
    for (int i = 1; i <= T; i++)
    {
        for (int j = 0; j < m; j++)
        {
            int id = orders[j].y, t = orders[j].x;
            if (t == i)
            {
                f[id] = true;
                score[id] += 2;
                if (score[id] > 5) st[id] = true;
            }
        }
        for (int j = 1; j <= n; j++)
            if (!f[j])
            {
                score[j]--;
                score[j] = max(score[j], 0);
                if (score[j] <= 3) st[j] = false;
            }
        memset(f, false, sizeof(f));
    }
    
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (st[i]) res++;
    
    printf("%d", res);
    
    return 0;
}

优化

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 100010;

int n, m, T;
int score[N], last[N];
bool st[N];
PII orders[N];

int main()
{
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < m; i++) scanf("%d%d", &orders[i].x, &orders[i].y);
    sort(orders, orders + m);
    
    for (int i = 0; i < m; )
    {
        int j = i;
        while (j < m && orders[j] == orders[i]) j++;
        
        int id = orders[i].y, t = orders[i].x, cnt = j - i;
        i = j;
        
        score[id] -= t - last[id] - 1;
        score[id] = max(0, score[id]);
        if (score[id] <= 3) st[id] = false;
        score[id] += 2 * cnt;
        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++)
        if (st[i]) res++;
        
    printf("%d", res);
    
    return 0;
}

参考

AcWing