C++枚举求解护盾晶石分配方案

好的，我们来分析并解决这个问题。这是一个典型的整数线性方程求解问题，核心是找出所有满足条件的非负整数解。 ### 🎯 问题分析 我们需要找到三个非负整数 `r` (红), `b` (蓝), `g` (绿)，满足： 1. **能量方程**： `5r + 3b + 1g = n` 2. **数量方程**： `r + b + g = m` 3. **非负约束**： `r >= 0`, `b >= 0`, `g >= 0` 这是一个包含两个方程的**三元一次不定方程组**。我们可以通过消元法将其转化为一个二元一次方程，然后进行枚举求解。 ### 🧠 解题思路 1. **消元**：将 `g = m - r - b` 代入能量方程 `5r + 3b + (m - r - b) = n`。 2. **简化**：合并同类项得到 `4r + 2b = n - m`。 3. **化简**：两边同时除以 2，得到 `2r + b = (n - m) / 2`。 * **关键条件**：`(n - m)` 必须是一个**非负偶数**，否则无解。 4. **枚举**：令 `k = (n - m) / 2`，则方程变为 `2r + b = k`。 * 我们可以枚举 `r` 从 0 开始。 * 对于每个 `r`，计算 `b = k - 2r`。 * `b` 必须满足 `b >= 0`。 * 由 `r >= 0` 和 `b >= 0` 可得 `r <= k / 2`，即 `r` 的最大值为 `k / 2`。 5. **计算 `g`**：一旦我们确定了满足条件的 `r` 和 `b`，就可以直接计算 `g = m - r - b`。 * 隐式条件：`g` 必须满足 `g >= 0`，即 `r + b <= m`。 * 因为 `r + b = r + (k - 2r) = k - r = (n - m)/2 - r`。 * 而 `g = m - (r+b) = m - ( (n-m)/2 - r) = (3m - n)/2 + r`。 * 我们可以不显式检查 `g >= 0`，而是在枚举 `r` 时，检查 `b >=0` 和 `r + b <= m`。但由于 `r+b = k - r`，条件等价于 `k - r <= m`。 6. **优化枚举**：为了让代码更简洁，我们可以直接枚举 `b`（蓝晶石），因为 `b` 的变化是连续的。 * 方程 `2r + b = k`。 * `b` 的取值范围是 `[0, k]`。 * 要求 `b` 与 `k` 的奇偶性相同（因为 `r = (k - b) / 2` 必须是整数，而这个要求是自动满足的，因为 `k` 是整数，`b` 也是整数，`k-b` 任何整数除以2，只要 `k`和`b` 同奇偶即可，但实际枚举中 `r`是整数，所以 `k-b` 必须为偶数）。 * **更好的枚举方式**：枚举 `r`，`r` 从 0 到 `k/2`，这样 `r` 自动为整数。然后 `b = k - 2r`，`g = m - r - b = m - r - (k - 2r) = m - k + r`。 * 我们只需要检查 `b >= 0` (已经满足) 和 `g >= 0` (即 `m - k + r >= 0`)。 ### 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; // 1. 检查是否为偶数且非负 int diff = n - m; if (diff < 0 || diff % 2 != 0) { // 无解，不输出任何内容 return 0; } int k = diff / 2; // 2. 枚举所有可能的红晶石数量 r // r 从 0 开始，最大值是 k/2 for (int r = 0; r <= k / 2; ++r) { int b = k - 2 * r; // 蓝晶石数量 int g = m - r - b; // 绿晶石数量 // 检查绿晶石数量是否非负 (隐含条件) // g = m - r - (k - 2r) = m - k + r // 由于 r <= k/2, 只需确保 m - k + r >= 0 if (g >= 0) { cout << r << " " << b << " " << g << endl; } } return 0; } ``` ### 📝 代码解释 * **头文件和命名空间**：`#include <iostream>` 提供输入输出流，`using namespace std;` 让我们可以直接使用 `cout` 和 `cin`。 * **读取输入**：`cin >> n >> m;` 从标准输入读取两个整数。 * **关键检查**： * `if (diff < 0 || diff % 2 != 0)`：这是数学推导出的必要条件。如果 `n - m` 为负数或奇数，题目无解，直接结束程序。这是一种**防御性编程**习惯，提前消除无效情况。 * **主循环**： * `for (int r = 0; r <= k / 2; ++r)`：枚举所有可能的红晶石数量。`r` 的上限是 `k/2`，因为 `b = k - 2r` 必须为非负数。 * `int b = k - 2 * r;`：根据公式 `2r + b = k` 直接计算出蓝晶石的数量。 * `int g = m - r - b;`：根据总数量公式计算出绿晶石的数量。 * `if (g >= 0)`：虽然我们的推导中 `g` 应该自动非负（当 `r` 在范围内时），但是加上这个检查可以确保万无一失，特别是当输入数据有边界情况时。这是一种**健壮性**处理。 * **输出**：`cout << r << " " << b << " " << g << endl;` 按格式输出，`endl` 表示换行。 ### ⚙️ 复杂度分析 * **时间复杂度**：O(m) 或 O(n/m)，实际是 O(k) 即 O(n-m)。在最坏情况下（n 很大，m 很小），循环次数约为 n/4，在题目给定的 n, m 范围内（1000MS/100MB），这个复杂度是完全可以接受的。 * **空间复杂度**：O(1)，只使用了几个变量，没有使用额外的数据结构。 ### 🧐 进阶建议与知识点 * **数学思维**：这道题的核心是**解线性丢番图方程**。将三元方程降维成二元方程是解这类问题的常见技巧。 * **边界条件**：要特别注意 `n - m` 的奇偶性。这是初学者最容易忽略的点。 * **防御性编程**：在函数的开头检查所有可能的错误输入或不合法状态，可以大大提高代码的鲁棒性。 * **可读性**：代码中的变量名 `r`, `b`, `g`, `diff`, `k` 虽然简短，但在本题上下文中是清晰的。对于更复杂的工程，建议使用更具描述性的名称，如 `redStone`, `blueStone`, `energyNeeded` 等。 ######[AI写代码神器 | 1809点数解答 | 2026-06-19 11:08:12]