Task 3 - Dispatching Orders [42.5 Marks]b

Cs, Go!

||最后更新: 2025-10-17|
 

总体思路

目标：
实现一个“订单调度系统”，能根据：
  • 用户饥饿程度（越饿优先送）
  • 距离餐厅远近（越近优先送）
      • 来决定订单派送顺序。

🧩 类结构概览

🍱 Order（订单类）

  • hunger: 用户饥饿程度（1–10，越大越饿）
  • location: 用户所在位置 (x, y)
  • distance: 订单到餐厅距离（后由 OrderDispatch 计算）
  • penalty_score: FoodFast™ 惩罚分（越低越优先）
惩罚分计算公式：
（距离越远惩罚越高，越饿惩罚越低。）

🚚 OrderDispatch（调度系统类）

属性：
  • dispatch_location: 派送点坐标
  • max_orders: 系统可容纳最大订单数
  • pending_orders: 存储当前待派送订单的最大堆（ArrayMaxHeap）
 
 
1️⃣
Task 3.1 - Receiving Orders
任务目标：
  • 将新订单加入堆中；
  • 若订单数已达上限，抛出异常；
  • 加入前先计算惩罚分（FoodFast 分数）。

🧠 实现思路

  1. 检查当前堆是否已满；
  1. 计算欧几里得距离（直线距离）；
  1. 根据公式计算 penalty_score；
  1. 插入到最大堆（堆自动保证最低分优先）。

🧾 伪代码

 
1️⃣
Task 3.2 - Fulfilling Orders
任务目标：
  • 从堆中取出惩罚分最低（优先级最高）的订单；
  • 若堆为空，抛出异常。

🧠 实现思路

  1. 检查堆是否为空；
  1. 使用堆的 extract_max()（因定义为 max_heap）；
  1. 返回被派送的订单对象。

🧾 伪代码

 
1️⃣
Task 3.3 - Delivery Runs
任务目标：
让无人机在一次出发中派送尽可能多的订单，但需保证：
无人机必须能送完所有分配订单后安全返回（不能超出 max_travel）。

🧠 实现思路

  1. 记录当前总行程（初始为 0），当前位置为派送点；
  1. 不断取出下一个最低惩罚分订单；
  1. 计算“到该订单 + 返回”的总距离；
  1. 若超出 max_travel，则停止；
  1. 否则派送该单，更新当前位置与总距离；
  1. 结果保存于 ArrayList 并返回。

🧾 伪代码

 
1️⃣
Task 3.4 [1054 ONLY] - Order Surge!
任务目标：
当系统同时接收到一批新订单（surge_batch）时：
  • 计算该批订单的平均惩罚分；
  • 只接收惩罚分 ≤ 平均值 的订单；
  • 保留原有订单；
  • 若超出容量，提前停止添加。

🧠 实现思路

  1. 遍历 surge_batch，计算平均惩罚分；
  1. 对每个新订单计算其 penalty；
  1. 若 penalty ≤ 平均值且系统未满，则加入；
  1. 若系统已有很多订单，可临时合并后堆化（heapify）。

🧾 伪代码

 
Loading...