P8685 [蓝桥杯 2019 省 A] 外卖店优先级--优先队列“数组”！！！！！

题目

解析

每个外卖店会在不同的时间点收到订单，我们可以看见测试用例的时间顺序是不同的，而且有在相同时间内有多个订单的店铺

如果我们按输入的顺序来计算，显而易见是求不出来的，所以我们需要按时间顺序来处理订单，然后计算优先级，并判断是否在优先缓存中。

那么问题来了，我们应该如何对时间进行排序，用数组然后用sort？但是一个id，对应了多个时间点，一维数组显然难以实现，用二维数组？（不知道行不行，但是我知道太复杂了）

这里我们会想要一个以id来区分的存储器存储时间点，并且能够对时间点排序

没错没错，就只有他了优先队列数组【优先队列还不行，优先队列不能存储id】

优先队列的作用：
1.按时间顺序处理订单，避免手动排序的复杂性。
2.不同下标的队列数组，内容互不影响。
3.时间复杂度：每个订单插入和取出操作的时间复杂度为 O(log m)，总复杂度为 O(m log m + n)，适用于大规模数据。

找到存取id和时间点的最佳容器后，我们需要遍历每一个id，计算时间点，判断是否在优先缓存中。

注意：题目中问的是t时刻，有些店铺在t时刻前就没有订单了，我们还需计算最后一个时刻到t时刻减少的优先级

if (last != t) {pri -= (t - last);if (pri < 0)pri = 0;}if (in && pri <= 3)in = false;

优先队列

priority_queue<int, vector<int>, greater<int>> h;

优先队列 (priority_queue)：
是 C++ 中一种特殊的数据结构，它和普通队列（先进先出）不同，元素的出队顺序由优先级决定。
它是 C++ STL 中的一种容器，默认是大顶堆（队首元素最大）。
但这里通过 greater 指定为小顶堆（队首元素最小）。
priority_queue 的完整模板参数列表如下：

如何判断是否使用优先队列？

1.是否要求动态获取最大值/最小值？
是 → 优先队列。
2.是否需要按特定顺序处理元素？
是 → 优先队列。
3.是否涉及贪心策略（每次选最优解）？
是 → 优先队列。

省略规则

template<class T,                          // 元素类型（必须明确指定）class Container = vector<T>,      // 底层容器（默认是 vector<T>）class Compare = less<T>          // 比较函数（默认是大顶堆）
> 
class priority_queue;

元素类型 T：必须明确指定（如 int）。

底层容器 Container：可以省略，默认用 vector。
比较函数 Compare：可以省略，默认用 less（大顶堆）。

什么时候可以完全省略？
大顶堆（默认行为）：可以省略底层容器和比较函数：

priority_queue<int> h; // 等价于 priority_queue<int, vector<int>, less<int>>

优先队列常用操作

大顶堆 vs 小顶堆

定义队列h

#include <bits/stdc++.h>
using namespace std;int main() {priority_queue<int, vector<int>, greater<int>> h; // 单个队列for (int i = 0; i < 3; i++) {int x;cin >> x;h.push(x); // 所有元素插入同一个队列}while (!h.empty()) {cout << h.top() << ' '; // 按小顶堆顺序输出：1 2 3h.pop();}return 0;
}

队列数组

下述定义的为队列数组h[n]，每个队列都是相互独立的，队列自动排序。

#include <bits/stdc++.h>
using namespace std;int main() {priority_queue<int, vector<int>, greater<int>> h[3]; // 3 个队列// 为每个队列插入多个元素h[0].push(3);h[0].push(1);h[0].push(2); // 队列0排序后：1 2 3h[1].push(5);h[1].push(4);              // 队列1排序后：4 5// 输出每个队列的内容for (int i = 0; i < 3; i++) {while (!h[i].empty()) {cout << h[i].top() << ' ';h[i].pop();}cout << endl;}return 0;
}

代码

#include <bits/stdc++.h>
using namespace std;
int n, t, m, cnt;int main() {cin >> n >> m >> t;//建优先队列数组priority_queue<int, vector<int>, greater<int>> h[100010];for (int i = 1; i <= m; i++) {int ts, id;cin >> ts >> id;h[id].push(ts);}//遍历每家店铺for (int i = 1; i <= n; i++) {int last = 0, pri = 0;//last:上一次订单时间，pri:记优先级bool in = false;//判定是否在优先级队列中//遍历商铺的所有订单while (!h[i].empty()) {int x = h[i].top();//x时刻h[i].pop();//判断是否有同一时刻多次订单if (last != x) {//计算时间差，减少优先级pri -= (x - last - 1);//优先级不能为负if (pri < 0)pri = 0;}//判定是否移除优先级if (in && pri <= 3)in = false;//增加优先级pri += 2;last = x;//判定是否加入缓存if (pri > 5) {in = true;}}//判断T时刻该店铺是否在优先缓存中if (last != t) {pri -= (t - last);if (pri < 0)pri = 0;}if (in && pri <= 3)in = false;if (in) {cnt++;}}cout << cnt;return 0;
}