wordpress网站数据库崩溃,无锡招标网官方网站,新葡京网址网站建设,网站源码怎样弄成网站题目
有N个餐厅和M个外卖员#xff0c;每个餐厅在某个时间点会产生一个外卖订单#xff0c;这些订单都有产生时间、所需送达时间和优先级。外卖员在空闲时会选择最优先的订单来配送#xff0c;直到所有订单都被送达。具体规则如下: 对于每个餐厅的订单#xff0c;优先级高…题目
有N个餐厅和M个外卖员每个餐厅在某个时间点会产生一个外卖订单这些订单都有产生时间、所需送达时间和优先级。外卖员在空闲时会选择最优先的订单来配送直到所有订单都被送达。具体规则如下: 对于每个餐厅的订单优先级高的订单优先其次是所需送达时间最短的订单再次是产生时间最早的订单。外卖员在空闲时会从所有餐厅的最高优先级订单中挑选一个所需送达时间最短的订单进行配送若所需送达时间相同则选择餐厅编号最小的订单。
输入描述
第一行三个数N、M、P分别表示有N个餐厅M个外卖员P个订单随后有P行每行有4个数字分别是餐厅编号、产生时间、优先级和所需送达时间。
输出描述
输出P行每行表示每个订单被送达的时间点。
示例
输入
2 2 4
1 1 2 5
1 4 3 2
2 2 1 4
2 5 2 1
输出
6
8
6
7
实现思路 订单的排序与优先队列 首先将所有订单按照产生时间进行排序。这样可以按照时间顺序逐步处理订单。使用一个优先队列 pq最大堆来存储当前时间点可以处理的订单并根据优先级、送达时间、餐厅编号的规则排序。 外卖员的空闲时间管理 使用一个最小堆 delivery_boys 来记录每个外卖员的空闲时间。最小堆确保我们总是优先分配订单给最早空闲的外卖员。 模拟订单分配 当前时间点为最早空闲的外卖员的空闲时间或者下一个订单的产生时间。将当前时间点之前产生的所有订单加入优先队列 pq 中。从 pq 中选择最优的订单分配给最早空闲的外卖员并更新外卖员的空闲时间。如果 pq 中没有订单时间推进到下一个订单产生的时间。 更新订单送达时间 外卖员选择订单后送达时间为外卖员当前空闲时间或订单产生时间取两者较大值加上订单的送达时间。记录每个订单的送达时间并将外卖员的空闲时间更新为新的送达时间。
C 代码
#include iostream
#include vector
#include queue
#include algorithmusing namespace std;struct Order {int restaurant;int start_time;int priority;int delivery_time;int index; // 记录订单的原始顺序
};// 定义优先级队列的排序规则
struct Compare {bool operator()(Order const a, Order const b) {if (a.priority ! b.priority) return a.priority b.priority;if (a.delivery_time ! b.delivery_time) return a.delivery_time b.delivery_time;return a.restaurant b.restaurant;}
};int main() {int N 2, M 2, P 4;vectorOrder orders(P);orders[0] {1,1,2,5,0};orders[1] {1,4,3,2,1};orders[2] {2,2,1,4,2};orders[3] {2,5,2,1,3};// 按产生时间排序sort(orders.begin(), orders.end(), [](Order const a, Order const b) {return a.start_time b.start_time;});vectorint result(P, 0);priority_queueOrder, vectorOrder, Compare pq;// 外卖员的空闲时间最小堆priority_queueint, vectorint, greaterint delivery_boys;// 初始化所有外卖员为空闲状态for (int i 0; i M; i) {delivery_boys.push(0);}int i 0;while (i P || !pq.empty()) {// 当前时间为最早的外卖员空闲时间或下一个订单的产生时间int current_time delivery_boys.top();if (i P) {current_time max(current_time, orders[i].start_time);}// 将当前时间之前产生的订单加入优先队列while (i P orders[i].start_time current_time) {pq.push(orders[i]);i;}if (!pq.empty()) {// 取出最早空闲的外卖员int delivery_boy_time delivery_boys.top();delivery_boys.pop();// 选择优先级最高的订单Order top_order pq.top();pq.pop();// 更新订单送达时间int delivery_time max(delivery_boy_time, top_order.start_time) top_order.delivery_time;result[top_order.index] delivery_time;// 更新外卖员的空闲时间delivery_boys.push(delivery_time);} else {// 如果当前没有订单可分配推进时间到下一个订单的产生时间if (i P) {delivery_boys.push(orders[i].start_time);}}}for (int i 0; i P; i) {cout result[i] endl;}return 0;
}
时间复杂度 初始排序 将订单按产生时间排序的时间复杂度为 O(PlogP)O(P \log P)O(PlogP)其中 PPP 是订单数量。 模拟分配过程 每个订单最多进入和弹出优先队列一次进入优先队列的时间复杂度为 O(logP)O(\log P)O(logP)。外卖员的空闲时间最小堆操作插入和弹出的时间复杂度为 O(logM)O(\log M)O(logM)其中 MMM 是外卖员的数量。总的模拟分配过程的时间复杂度为 O(PlogPPlogM)O(P \log P P \log M)O(PlogPPlogM)。
综合考虑时间复杂度为 O(PlogPPlogM)O(P \log P P \log M)O(PlogPPlogM)。
空间复杂度 优先队列 pq 和 delivery_boys 优先队列 pq 最多存储 PPP 个订单因此空间复杂度为 O(P)O(P)O(P)。最小堆 delivery_boys 始终存储 MMM 个外卖员的空闲时间因此空间复杂度为 O(M)O(M)O(M)。 其他存储 orders 数组存储 PPP 个订单的信息因此空间复杂度为 O(P)O(P)O(P)。result 数组存储每个订单的送达时间因此空间复杂度为 O(P)O(P)O(P)。
综合考虑空间复杂度为 O(PM)O(P M)O(PM)。
