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;
}