IT评测·应用市场-qidao123.com

标题: P8685 [蓝桥杯 2019 省 A] 外卖店优先级--优先队列“数组”！！！！！ [打印本页]

作者: 小小小幸运 时间: 2025-3-11 19:39
标题: 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;}

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)