不能直接贪心,该怎么办?以真题B4071 [GESP202412 五级] 武器强化,讲解互相制约问题的解题思路

这类“枚举答案 / 固定条件”（在算法竞赛中通常被称为“枚举答案法”或“参数搜索”）的解题思路，在 GESP 考级中不仅非常常见，而且是拉开分数差距的“分水岭”级别考点。

特别是在 四级（排序/贪心入门）到 六级（图论/动态规划） 这个阶段，出题人非常喜欢用这类题来考察学生从“线性思维”到“非线性思维”的转变。

“构造不成用枚举，贪心不行固定条件”

一： GESP C++ 五级《武器强化》解题思想

（一）题目核心矛盾

• 双目标冲突：既要让武器1的数量尽可能多，又要让其他武器数量严格小于武器1。

• 直接贪心失效：仅按“修改费用最低”选择材料，可能永远无法压制某个数量庞大的对手武器。

（二）破局关键：从“构造”转向“枚举”

当直接构造最优解困难时，考虑枚举答案，将问题转化为判定性问题：

• 无法直接计算“最少花费”，但可以判断“若武器1有 k个材料，能否实现且花费多少”。

• 枚举所有可能的 k（武器1的最终数量），取最优解。

（三）、固定条件后的贪心策略

对每个固定的 k，问题简化为：

如何用最少花费，使武器1数量 =k，且其他武器数量 ≤k−1？

贪心分两步：

1. 强制削弱（削峰）

• 遍历其他武器，若某武器材料数 ≥k，必须削减至 k−1。

• 贪心原则：优先移除该武器中修改费用最小的材料（转为武器1），以最小代价减少对手数量。

2. 查漏补缺（补足）

• 若武器1数量仍不足 k，从所有剩余未处理材料中选择费用最小的补充给武器1。

（四）、完整算法流程

1. 统计各武器初始材料及其修改费用，并对每个非1武器的材料费用排序。

2. 枚举 k从 初始武器1数量到 总材料数。

3. 对每个 k：

• 初始化花费为0，武器1当前数量为初始值。

• 遍历其他武器，执行“强制削弱”，累加花费并增加武器1数量。

• 若武器1数量仍小于 k，从剩余材料池中选取最便宜材料补足，累加花费。

• 更新全局最小花费。

4. 输出最小花费。

（五）、思维启示与适用场景

• 适用场景：存在多个互相制约的目标，且目标之间难以同时优化时。

• 通用技巧：

• 当直接贪心无法同时满足所有条件 → 枚举某个关键变量（如答案、阈值）。

• 将动态对抗问题转化为静态约束问题 → 固定条件后贪心验证。

• 复杂度权衡：枚举范围较小（m≤1000）时，即使内层贪心为 O(mlogm)，整体也可接受。

 二、总结 “枚举+贪心”类题目的 3 个规律

当看到以下特征的题目时，这题大概率需要考虑“枚举答案”！

规律 1：出现“最值中的最值”或“满足条件的最小值/最大值”

题干通常会隐藏一个无法直接求出的核心变量，要求在满足一系列复杂约束的前提下，求这个变量的最值。

• 标志性词句：“最少需要多少时间”、“最小的总花费”、“最大的最小值”、“最小的最大价值”。

• 应对：直接求最值太难，干脆枚举这个最值，然后把问题转化为“判断这个数值是否成立”。

规律 2：存在相互制约的“双目标”或“多目标”

就像《武器强化》，要求 A 尽量大，同时 B 尽量小，或者 A 必须大于 B。单一的贪心策略往往只能顾全一头。

• 应对：固定其中一个目标（枚举 A 的值），这样另一个目标（控制 B）就变成了在约束条件下的单目标优化，此时往往可以使用简单的贪心或数学公式直接算出结果。

规律 3：数据范围暗示可以“暴力枚举答案”

这是最实在的一条规律。GESP 的题目非常讲究“复杂度估算”。

• 如果总材料数/总人数/总天数（N）的范围是 N≤1000或 N≤105。

• 而单次检查的复杂度是 O(NlogN)或 O(N)。

• 应对：算一下总复杂度，如果 枚举次数 × 单次检查复杂度不会超时（通常在 107∼108以内），大胆去枚举就对了！

 进阶补充： 如果题目给的数据范围非常大（比如 N≤109），枚举就会超时。这时候规律依然适用，只是要把“线性枚举”升级为“二分查找枚举”（也就是所谓的“二分答案”），这在 GESP 六级以上是绝对的高频考点。

三、 GESP 中高阶考级的其他 3 大“类型”

除了“枚举+贪心”，在近期的 GESP 四级、五级、六级的真题中，还有一些几乎每年必考的经典题型。

类型 1：滑动窗口 / 双指针（针对“连续子数组/子串”问题）

• 出题特征：要求寻找满足某种条件的连续一段元素，求最值或方案数。

• 经典例题：最长无重复字符的子串、和不超过 K 的最长子数组、含有所有特定字符的最短子串。

• 破局点：涉及“连续性”和“区间最值”时，先考虑能不能用两个指针（左、右）在 O(N)的时间内滑过整个数组解决。

类型 2：前缀和 / 差分（针对“频繁区间查询/修改”问题）

• 出题特征：给定一个初始数组，随后有海量的“将区间 [L, R] 加上一个数”或“求区间 [L, R] 的和”的操作。

• 经典例题：区间加减后的最终数组、快速判断某个子矩阵的总和。

• 破局点：如果老老实实按题意去循环模拟，复杂度往往是 O(N×Q)直接超时。看到“区间操作”四个字，立刻想到用前缀和（化区间为两点之差）或差分（化逐个加为边界加减）将复杂度降维到 O(N+Q)。

类型3：动态规划 DP（针对“最优决策序列”问题）

• 出题特征：题目问“最多能获得多少价值”、“有多少种方案”，并且当前的选择会影响后面的状态。

• 经典例题：0-1背包（选或不选）、最长公共子序列、网格中的最短路径数。

• 破局点：寻找状态转移方程。自底向上（打表）或自顶向下（记忆化搜索）计算，避免重复计算重叠子问题。

 四、 备考建议

GESP 的命题组（由全国信息学奥赛（NOI）科学委员会主导）非常注重知识点在实际场景中的应用，而不会出纯粹的数学偏题。

如果想要在接下来的考级中稳扎稳打：

1. 建立“条件反射”：拿到题先别急着敲代码，花 3 分钟时间用上面的“规律”给题目定个位。

2. 手写小数据推演：对于贪心和动态规划题，手动列一个 3~5 个小数据的表格，往往能直接看出递推关系或贪心策略的正确性。

3. 控制边界条件：GESP 阅卷极其严格，多测点（Subtask）机制下，一定要特判 n=0、n=1或者“无解”的情况。