求计算男孩剩余苹果数量的算法（含场景示例）

问题背景 #

现有n个男孩，每人持有一定数量的苹果，示例数据如下：

boys = {"b1": 20, "b2": 60, "b3": 10, "b4": 100}

另有T辆卡车，每辆卡车需要装填指定数量的苹果，装填时需从索引从低到高的男孩处依次取苹果，卡车装填需求示例如下：

trucks = 
{
    "t1": [50, ["b1", "b2"]],
    "t2": [20, ["b1", "b2", "b3"]],
    "t3": [20, ["b3", "b4"]],
}

装填规则：按男孩索引从低到高顺序取苹果，例如装填t1时，先取b1的20个苹果，剩余40个从b2处取，取完后b1剩余0个，b2剩余20个。

算法设计步骤 #

1. 固定男孩顺序 #

因为装填依赖索引高低顺序，首先要把男孩数据转换为有序结构（比如有序列表或有序字典），明确全局的索引排序规则（例如按男孩标识的自然顺序、输入顺序等）。示例中可整理为：

ordered_boys = [("b1", 20), ("b2", 60), ("b3", 10), ("b4", 100)]
# 或用字典维护剩余量，同时单独存储顺序列表
boys_remaining = {"b1":20, "b2":60, "b3":10, "b4":100}
boy_order = ["b1", "b2", "b3", "b4"]

2. 逐个处理卡车装填需求 #

对每辆卡车执行以下流程：

• 提取卡车的需求总量required和指定的男孩列表target_boys
• 把target_boys按照全局的boy_order排序，确保取苹果的顺序严格遵循索引从低到高
• 遍历排序后的target_boys，依次取苹果：
  • 若当前男孩剩余苹果量current ≤ required：取走全部苹果，required减去current，该男孩剩余量设为0
  • 若当前男孩剩余苹果量current > required：取走required个苹果，required设为0，该男孩剩余量更新为current - required
  • 当required减至0时，停止当前卡车的装填操作

3. 查询剩余苹果量 #

处理完所有卡车后，直接从boys_remaining字典或ordered_boys有序结构中查询对应男孩的剩余数值即可；若需要中途查询，可在每处理完一辆卡车后实时更新数据，随时支持查询。

示例模拟处理过程 #

以题目示例为例：

1. 初始状态：boys_remaining = {"b1":20, "b2":60, "b3":10, "b4":100}
2. 处理t1（需求50，目标["b1","b2"]）：
   • 取b1全部20个，剩余需求30，b1剩余0
   • 从b2取30个，剩余需求0，b2剩余30
   • 更新后：boys_remaining = {"b1":0, "b2":30, "b3":10, "b4":100}
3. 处理t2（需求20，目标["b1","b2","b3"]）：
   • b1剩余0，跳过，需求仍为20
   • 从b2取20个，剩余需求0，b2剩余10
   • 更新后：boys_remaining = {"b1":0, "b2":10, "b3":10, "b4":100}
4. 处理t3（需求20，目标["b3","b4"]）：
   • 取b3全部10个，剩余需求10，b3剩余0
   • 从b4取10个，剩余需求0，b4剩余90
   • 最终状态：boys_remaining = {"b1":0, "b2":10, "b3":0, "b4":90}

实现注意事项 #

• 必须保证男孩顺序的全局一致性，所有取苹果操作严格遵循预先定义的索引顺序
• 处理卡车指定的男孩列表时，必须先按全局顺序排序，避免出现顺序错误
• 用字典维护剩余量可提升查询和更新的效率，适合大规模数据场景

内容的提问来源于stack exchange，提问作者Hazem Elmahy