机器人能源模块题解
2026-07-23 09:11:51
发布于：广东
一、题目大意
机器人有 项能源指标，第 项指标至少要达到 need[j]。
现在有 个能源模块，第 个模块能够为每一项指标提供一定的增益。每个模块最多只能选择一次。
我们需要找到一组模块，使得：
- 每一项能源指标的总和都不小于最低需求；
- 选择的模块数量尽可能少；
- 如果最少模块数量相同，选择的模块编号序列要字典序最小。
输出时，模块编号按照从小到大的顺序输出。
二、观察数据范围
题目中：
每个模块只有两种状态：
- 不选择；
- 选择。
因此，所有选择方案的数量为：
当 时：
只有三万多种方案，可以把每一种方案都检查一遍。
所以这道题可以直接使用 二进制枚举所有子集。
三、什么是二进制枚举子集
假设一共有 3 个模块。
我们可以使用一个二进制数表示模块的选择情况：
| 二进制状态 | 选择的模块 |
|---|---|
000 |
一个都不选 |
001 |
选择模块 1 |
010 |
选择模块 2 |
011 |
选择模块 1、2 |
100 |
选择模块 3 |
101 |
选择模块 1、3 |
110 |
选择模块 2、3 |
111 |
选择模块 1、2、3 |
对于一个整数 mask，如果：
(mask >> i) & 1
等于 1，就表示选择第 个模块。
之所以是 ，是因为程序中的下标从 0 开始，而题目中的模块编号从 1 开始。
四、如何判断一个方案是否合法
枚举出一个方案后，我们计算它在每一项能源指标上的总增益。
假设当前方案选择了若干模块，我们用：
sum[j]
表示这些模块在第 项指标上提供的总增益。
如果对于所有指标都满足：
那么当前方案就是一个可行方案。
只要有一项不满足要求，当前方案就不能使用。
五、如何选择最优答案
对于每一个可行方案，我们需要按照以下顺序比较。
1. 先比较模块数量
模块数量更少的方案一定更优。
例如：
- 方案 A 选择 2 个模块；
- 方案 B 选择 3 个模块。
那么无论它们的模块编号是什么，方案 A 都更优。
2. 模块数量相同时比较字典序
例如有两个方案：
1 4
2 3
比较第一个位置：
- 第一个方案是 1；
- 第二个方案是 2。
因为 ，所以：
1 4
的字典序更小。
再例如：
1 3 5
1 4 2
第一个位置相同，继续比较第二个位置：
- 3 小于 4；
所以第一个序列字典序更小。
在 C++ 中，vector<int> 可以直接使用 < 比较，比较规则就是字典序：
chosen < best
六、完整思路
依次枚举从 0 到 的每一个二进制状态。
对于每个状态：
- 统计选择了多少个模块；
- 记录选择的模块编号；
- 计算每一项能源指标的总增益；
- 判断是否满足全部最低要求；
- 如果满足要求，就与当前最优方案比较：
- 模块数量更少，则更新答案；
- 模块数量相同但编号序列字典序更小，也更新答案。
题目保证至少存在一个可行方案，所以最后一定能够找到答案。
七、样例推演
最低需求为：
100 200 300 400
三个模块分别提供：
模块 1：50 50 50 50
模块 2：200 300 200 300
模块 3：900 150 389 399
只选择一个模块时：
- 模块 1 不满足；
- 模块 2 的第 3、4 项不满足；
- 模块 3 的第 2、4 项不满足。
因此至少需要选择两个模块。
选择模块 1 和模块 3 后，总增益为：
即：
950 200 439 449
所有指标都达到了要求，因此这是一个可行方案。
最终输出：
2 1 3
这里空空如也
有帮助，赞一个