蓝桥杯P1259-奇怪的馈赠 （贪心题解）

题目：奇怪的捐赠

题目来源：1.奇怪的捐赠 - 蓝桥云课

题目描述

需要将 100 万（1,000,000）正好分成若干个 7 的次方形式的数（如 7^0=1, 7^1=7, 7^2=49 等），且每种金额（即每个 7 的次方）的使用次数不能超过 5 份。

解题思路

1. 列出所有小于 100 万的 7 的次方：

   • 计算 7 的各次方：7^0 = 1, 7^1 = 7, 7^2 = 49, 7^3 = 343, 7^4 = 2401, 7^5 = 16807, 7^6 = 117649, 7^7 = 823543。
   • 注意 7^8 = 5764801 已超过 100 万，因此只取 7^0 到 7^7。

2. 贪心策略：

   • 从最大的 7 的次方（823543）开始，尽可能多地使用，但不超过 5 次。
   • 计算剩余金额，再对次大的 7 的次方重复此过程，直到剩余金额为 0 或无法继续分解。

3. 实现步骤：

   • 用数组存储 7 的次方。
   • 从大到小遍历数组，计算当前金额能用几次该次方（不超过 5 次）。
   • 更新剩余金额并记录使用的总份数。
   • 最后检查是否正好分解为 100 万。

代码实现

#include <iostream>
using namespace std;int main() {ios::sync_with_stdio(0);  // 加速输入输出cin.tie(0); cout.tie(0);int sum = 0;           // 记录总份数int num = 1000000;     // 初始金额 100 万// 7 的次方数组，从 7^0 到 7^7int ter[] = {1, 7, 49, 343, 2401, 16807, 117649, 823543}; // 从最大的 7 的次方（索引 7）到最小的（索引 0）for (int i = 7; i >= 0; i--) { int temp = num / ter[i];  // 计算当前金额能用几次 ter[i]if (temp > 5) {           // 限制最多使用 5 次temp = 5;}sum += temp;              // 累加使用的份数num -= temp * ter[i];     // 更新剩余金额}// 检查是否正好分解完成if (num == 0) {cout << sum << endl;      // 输出总份数} else {cout << "无法用给定条件表示 1000000。" << endl;}return 0;
}

运行结果分析

计算过程：

1. num = 1000000，ter[7] = 823543：
   • 1000000 / 823543 = 1 < 5，取 1 次，sum = 1，num = 1000000 - 823543 = 176457。
2. num = 176457，ter[6] = 117649：
   • 176457 / 117649 = 1 < 5，取 1 次，sum = 2，num = 176457 - 117649 = 58808。
3. num = 58808，ter[5] = 16807：
   • 58808 / 16807 = 3 < 5，取 3 次，sum = 5，num = 58808 - 3 * 16807 = 8387。
4. num = 8387，ter[4] = 2401：
   • 8387 / 2401 = 3 < 5，取 3 次，sum = 8，num = 8387 - 3 * 2401 = 1184。
5. num = 1184，ter[3] = 343：
   • 1184 / 343 = 3 < 5，取 3 次，sum = 11，num = 1184 - 3 * 343 = 155。
6. num = 155，ter[2] = 49：
   • 155 / 49 = 3 < 5，取 3 次，sum = 14，num = 155 - 3 * 49 = 8。
7. num = 8，ter[1] = 7：
   • 8 / 7 = 1 < 5，取 1 次，sum = 15，num = 8 - 7 = 1。
8. num = 1，ter[0] = 1：
   • 1 / 1 = 1 < 5，取 1 次，sum = 16，num = 1 - 1 = 0。

输出：

• num = 0，说明 100 万被成功分解。
• sum = 16，即需要 16 份。

最终输出：16

注意事项

1. 正确性验证：

   • 823543 * 1 + 117649 * 1 + 16807 * 3 + 2401 * 3 + 343 * 3 + 49 * 3 + 7 * 1 + 1 * 1 = 1,000,000。
   • 每项使用次数均不超过 5，符合条件。

2. 边界情况：

   • 如果题目金额不是 100 万，需检查是否能被 7 的次方分解且满足限制条件。

3. 优化空间：

   • 当前代码已足够高效，时间复杂度为 O(1)，因为数组长度固定。

4. 注意 $7^0$ 也算 7 的若干次方，主包这里没注意成蠢货了。