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

题目

分析

每个外卖店会在不同的时间点收到订单，我们可以看见测试用例的时间顺序是不同的，而且有在相同时间内有多个订单的店肆
如果我们按输入的顺序来盘算，显而易见是求不出来的，以是我们必要按时间顺序来处理订单，然后盘算优先级，并判断是否在优先缓存中。
那么问题来了，我们应该如何对时间举行排序，用数组然后用sort？但是一个id，对应了多个时间点，一维数组显然难以实现，用二维数组？（不知道行不行，但是我知道太复杂了）
这里我们会想要一个以id来区分的存储器存储时间点，并且能够对时间点排序
没错没错，就只有他了优先队列数组【优先队列还不行，优先队列不能存储id】
优先队列的作用：
1.按时间顺序处理订单，避免手动排序的复杂性。
2.不同下标的队列数组，内容互不影响。
3.时间复杂度：每个订单插入和取出操纵的时间复杂度为 O(log m)，总复杂度为 O(m log m + n)，适用于大规模数据。
找到存取id和时间点的最佳容器后，我们必要遍历每一个id，盘算时间点，判断是否在优先缓存中。
注意：题目中问的是t时刻，有些店肆在t时刻前就没有订单了，我们还需盘算最后一个时刻到t时刻淘汰的优先级

1. if (last != t) {
2.                         pri -= (t - last);
3.                         if (pri < 0)
4.                                 pri = 0;
5.                 }
6.                 if (in && pri <= 3)
7.                         in = false;

复制代码

优先队列

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

复制代码

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

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

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

复制代码

元素类型 T：必须明确指定（如 int）。
底层容器 Container：可以省略，默认用 vector。
比力函数 Compare：可以省略，默认用 less（大顶堆）。
什么时候可以完全省略？
大顶堆（默认行为）：可以省略底层容器和比力函数：

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

复制代码

优先队列常用操纵

大顶堆 vs 小顶堆

界说队列h

1. #include <bits/stdc++.h>using namespace std;int main() {    priority_queue<int, vector<int>, greater<int>> h;
2. // 单个队列    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]，每个队列都是相互独立的，队列自动排序。

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

复制代码

代码

1. #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) {
2.                         pri -= (t - last);
3.                         if (pri < 0)
4.                                 pri = 0;
5.                 }
6.                 if (in && pri <= 3)
7.                         in = false;
8.                 if (in) {                        cnt++;                }        }        cout << cnt;        return 0;}

复制代码

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