P8685-蓝桥杯-2019-省-A-外卖店优先级-优先队列数组
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 3
h.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 3
h[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;
}