蓝桥杯 2019省赛 C/C++ A TG
题目¶
“饱了么”外卖系统中维护着 NN 家外卖店，编号 1∼N1∼N。
每家外卖店都有一个优先级，初始时 (00 时刻) 优先级都为 00。
每经过 11 个时间单位，如果外卖店没有订单，则优先级会减少 11，最低减到 00；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 22。
如果某家外卖店某时刻优先级大于 55，则会被系统加入优先缓存中；如果优先级小于等于 33，则会被清除出优先缓存。
给定 TT 时刻以内的 MM 条订单信息，请你计算 TT 时刻时有多少外卖店在优先缓存中。
输入格式
第一行包含 33 个整数 N,M,TN,M,T。
以下 MM 行每行包含两个整数 tsts 和 idid，表示 tsts 时刻编号 idid 的外卖店收到一个订单。
输出格式
输出一个整数代表答案。
数据范围
1≤N,M,T≤10^5,
1≤ts≤T,1≤ts≤T,
1≤id≤N,1≤id≤N输入样例：
2 6 6 1 1 5 2 3 1 6 2 2 1 6 2输出样例：
1样例解释
6 时刻时，1号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。
所以是有 1家店 (2 号) 在优先缓存中。
思路
对于该问题，假设$t_1$、$t_2$、$t_3$时刻有订单，并且$t_1\le t_2 \le t_3 <T$，则需要分别考虑$1\sim t_1-1$ 、$t_1+1 \sim t_2-1$、$t_2+1 \sim t_3-1$、$t_3+1 \sim T$和$t_1$、$t_2$、$t_3$ 、$T$两部分，前一部分是没有订单的部分，需要减去这些时刻*1，后一部分是有订单的部分，需要加上2*订单数（考虑到同一时刻有多个订单）。将订单信息按照时间排序，相同时间按照商店id排序。接着for循环遍历订单，找到相同的订单（时间、商店相同），处理订单时间$t-1-last[id]$，小于0则置零，小于3则设置优先缓存为false，然后处理订单时刻，加上2*订单数，如果优先级大于5，则设置优先缓存为true，最后令last[id]=t。
如果处理的最后时刻小于T，那么需要减去$T-last[i]$，即处理$last[i]+1 \sim T$部分，若优先级小于等于3，则设置优先缓存为false，最后循环所有优先缓存统计true个数输出即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int stores[MAXN], last[MAXN];
bool f[MAXN];
struct Order
{
int t, id;
};
vector<Order> orders;
bool cmp(Order a, Order b)
{
if (a.t == b.t)
return a.id < b.id;
return a.t < b.t;
}
int main()
{
int N, M, T;
cin >> N >> M >> T;
for (int i = 0; i < M; i++)
{
Order cur;
cin >> cur.t >> cur.id;
orders.push_back(cur);
}
sort(orders.begin(), orders.end(), cmp);
for (int i = 0; i < M;)
{
int j = i;
while (orders[i].id == orders[j].id && orders[i].t == orders[j].t && j < M)
j++;
int cnt = j - i;
int id = orders[i].id, t = orders[i].t;
i = j;
stores[id] -= t - last[id] - 1;
if (stores[id] < 0)
stores[id] = 0;
if (stores[id] <= 3)
f[id] = false;
stores[id] += cnt * 2;
if (stores[id] > 5)
f[id] = true;
last[id] = t;
}
for (int i = 1; i <= N; i++)
{
if (last[i] < T)
{
stores[i] -= T - last[i];
if (stores[i] <= 3)
f[i] = false;
}
}
int ans = 0;
for (int i = 1; i <= N; i++)
if (f[i])
ans++;
cout << ans << endl;
return 0;
}
