)
题目描述
“饱了么”外卖系统中维护着 N 家外卖店，编号 1 ~ N。每家外卖店都有一个优先级，初始时（0 时刻）优先级都为 0。
每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。
如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果优先级小于等于 3，则会被清除出优先缓存。
给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优先缓存中。
输入格式
第一行包含 3 个整数 N 、 M 和 T。
以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到一个订单。
输出格式
输出一个整数代表答案。
输入
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
输出
1
说明/提示
样例解释
6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6，加入优先缓存。所以有 1 家店（2 号店）在优先缓存中。
评测用例规模与约定
对于 80% 的评测用例，1≤N,M,T≤10000。
对于所有评测用例，1≤N,M,T≤10^5，1≤ts≤T，1≤id≤N。
#include <stdio.h> #include <stdlib.h> #define MAX_N 100010 typedef struct { int time; int id; } Order; // 比较函数：先按店铺id排序，id相同的按时间排序 int cmp(const void *a, const void *b) { Order *x = (Order *)a; Order *y = (Order *)b; if (x->id != y->id) { return x->id - y->id; } return x->time - y->time; } int main() { int N, M, T; scanf("%d %d %d", &N, &M, &T); Order orders[M]; for (int i = 0; i < M; i++) { scanf("%d %d", &orders[i].time, &orders[i].id); } // 按店铺和时间排序订单 qsort(orders, M, sizeof(Order), cmp); // 初始化每个店铺的状态 int priority[MAX_N] = {0}; // 用于计算优先级 int last_time[MAX_N] = {0}; // 上一次有订单的时间，用于和当前订单时间作差，找到要减去的数值 int in_cache[MAX_N] = {0}; // 是否在优先缓存中。如果是1就说明在优先缓存中，初始化为0，因为一开始肯定没在优先缓存中 int result = 0;//用于输出最后结果 int idx = 0; // 当前处理的订单索引 //订单索引就是订单的下标。共有M条订单，所以条件就是idx<M。 // 遍历每个店铺。一个店铺一个店铺的遍历，完全处理完一个店铺之后，即找到该店铺是否在缓存中后，再遍历其他店铺。 for (int id = 1; id <= N; id++) { // 处理该店铺，即店铺1的所有订单 //while循环的条件就是判断是否是店铺1，是店铺1才进行下面操作。 while (idx < M && orders[idx].id == id) { int ts = orders[idx].time;//当前的时刻赋值给ts。 // 计算从上一次订单到这次订单之间减少的优先级 if (last_time[id] != ts) { priority[id] -= (ts - last_time[id] - 1); if (priority[id] < 0) priority[id] = 0; } // 检查是否要移出缓存 if (in_cache[id] && priority[id] <= 3) { in_cache[id] = 0;//表示不在优先缓存里边 } // 处理当前订单 priority[id] += 2; last_time[id] = ts;//当前时间处理完成，下一次进行的时候就变成上一时刻了。 // 检查是否要加入缓存 if (priority[id] > 5) { in_cache[id] = 1; } idx++;//不断加1，直到处理完该店铺的所有订单 } // 处理从最后一次订单到T时刻的优先级减少 //避免出现最后一次时刻不在样例输入中，但店铺还是要减优先级的情况。最后再进行一次缓存判断，输出结果。 if (last_time[id] < T) { priority[id] -= (T - last_time[id]); if (priority[id] < 0) priority[id] = 0; if (in_cache[id] && priority[id] <= 3) { in_cache[id] = 0; } } // 统计结果 if (in_cache[id]) { result++; } } printf("%d\n", result); return 0; }int cmp(const void *a, const void *b) { Order *x = (Order *)a; Order *y = (Order *)b; if (x->id != y->id) { return x->id - y->id;//先按店铺id升序 } return x->time - y->time;//id相同按时间排序 }上述代码是快速排序，下面详细解析一下：
Order *x = (Order *)a; // 将void指针转换为Order指针
转换：
(Order *)a告诉编译器："把a当作指向Order的指针"使用：现在
x是Order *，可以用x->id访问成员
注意上述排序顺序。一开始我以为只需要进行时刻排序，但发现反正还要进行优先级减法，所以都一样。
怎样保证是升序还是降序呢？
| 升序（小在前） | 返回<0 | 返回>0 | return a - b |
| 降序（大在前） | 返回>0 | 返回<0 | return b - a |
对于升序比较函数：return a-b
| 情况 | 返回值 | 含义（升序视角） | 排序结果 |
|---|---|---|---|
a < b | 负数 | "a比b小，应该在前" | a在b前 |
a = b | 零 | "a和b相等" | 顺序不确定 |
a > b | 正数 | "a比b大，应该在后" | b在a前 |
对于降序比较函数：return b-a
| 情况 | 返回值 | 含义（降序视角） | 排序结果 |
|---|---|---|---|
a > b | 负数 | "a比b大，应该在前" | a在b前 |
a = b | 零 | "a和b相等" | 顺序不确定 |
a < b | 正数 | "a比b小，应该在后" | b在a前 |
例子：数字 3 和 5
情况1：升序比较函数
int cmp_asc(const void *a, const void *b) { int x = *(int *)a; // 假设 a=3, b=5 int y = *(int *)b; return x - y; // 3-5 = -2 < 0 }返回负数（-2）
指令："把 3 放在 5 前面"
结果：
3, 5（升序）
情况2：降序比较函数
int cmp_desc(const void *a, const void *b) { int x = *(int *)a; // 假设 a=3, b=5 int y = *(int *)b; return y - x; // 5-3 = 2 > 0 }返回正数（2）
指令："把 3 放在 5 后面"
结果：
5, 3（降序）
