2026世界机器人大赛真题：物资合并调度解析

NOIP编程小助手 · 算法真题拆解

在世界机器人大赛的「算法应用」赛项里，补给物资的合并调度是高频题型：把一堆堆零散物资合并成整箱，每次合并的花费等于两堆重量之和，怎样合并最省钱？这正是哈夫曼树（Huffman）/ 贪心 + 优先队列的经典考场模型。

一、原创题目

【物资合并调度】火星补给基地有 n 堆零散物资，第 i 堆重 w[i]。每次可以选任意两堆合并成一堆，花费为这两堆重量之和。反复合并直到只剩 1 堆，求最小总花费。

输入：第一行 n；第二行 n 个整数 w[i]。输出：最小总花费。

  

二、算法思路：每次挑最轻的两堆

贪心策略：每次都取当前最轻的两堆先合并。直觉上，越早合并的堆，在后续会被反复累加更多次，所以最轻的应被加最多次——这恰好是哈夫曼编码的「带权路径长度最小」思想。用小根堆（优先队列）即可在 O(n log n) 内完成。

1. 把所有重量放进小根堆；
2. 只要堆里多于 1 个元素，弹出最轻的 a 和次轻的 b；
3. 花费累加 a+b，把 a+b 重新压回堆；
4. 最后堆中剩下的唯一元素即最小总花费。

三、参考代码（C++ 版）

#include <bits/stdc++.h> using namespace std; int main() {     int n; cin >> n;     priority_queue<long long, vector<long long>, greater<long long>> pq;     for (int i = 0; i < n; i++) {         long long x; cin >> x;         pq.push(x);     }     long long ans = 0;     while (pq.size() > 1) {         long long a = pq.top(); pq.pop();         long long b = pq.top(); pq.pop();         long long s = a + b;         ans += s;         pq.push(s);     }     cout << ans << endl;     return 0; }

四、参考代码（Python 版）

import heapq n = int(input()) a = list(map(int, input().split())) heapq.heapify(a) ans = 0 while len(a) > 1:     x = heapq.heappop(a)     y = heapq.heappop(a)     s = x + y     ans += s     heapq.heappush(a, s) print(ans)

  

五、考点拆解（必看）

• 小根堆方向
  ：C++ priority_queue 默认是大根堆，必须显式写 greater<long long>；Python 用 heapq 本身即小根堆。
• 数据类型
  ：重量累加可能超 int，统一用 long long。
• 贪心正确性
  ：可交换论证——若存在非最轻两堆先合并的方案更优，交换后总花费不增，故贪心最优。
• 易错点
  ：堆中元素个数判断用 >1 而非 !=1；输入可能含重复重量。

六、进阶思考

若限制「每堆最多与 k 堆合并」（k 叉哈夫曼），需补虚拟堆使 (n-1)%(k-1)==0；叶子深度恰好等于该物资被合并的次数。试把题目改成「求合并顺序使最大单次花费最小」，思路会转向哪里？

七、互动引导

你在比赛里还遇到过哪些「合并 / 合并代价最小」的题？欢迎在评论区留言，下期我们拆解多源最短路的考场套路。关注 NOIP编程小助手，每天一题搞懂一个算法。

📚 免费少儿编程资料（夸克网盘领取）

以下资料来自夸克网盘分享。个人号链接暂不支持直接点击，请长按或复制下方链接，打开夸克网盘 App / 网页粘贴即可保存：

1. 1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
   https://pan.quark.cn/s/93995d3cb150
2. 2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
   https://pan.quark.cn/s/da97b5dbf75d
3. 3. Python背记手册.pdf
   https://pan.quark.cn/s/7568ae9ca92b
4. 4. Python课程
   https://pan.quark.cn/s/a94bf02d00c6
5. 5. 2024信息素养大赛图形化复赛集训题答案3-9
   https://pan.quark.cn/s/6ccab7ec3cbc
6. 6. 2025年03月份电子学会考级真题
   https://pan.quark.cn/s/4403c4228912
7. 7. 2025全国青少年信息素养大赛赛项说明
   https://pan.quark.cn/s/d9d0df4a9f29
8. 8. 青少儿信息素养大赛编程资料
   https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注本号第一时间获取新分享。