环保能量球 题解

题目分析

小杨每走 1 公里 就能获得 1 点 基础环保能量。同时，每走满 x 公里 会额外获得 1 点 奖励能量。已知小杨一共走了 n 公里，要求计算总共获得的能量点数。

关键点：

• 基础能量：每公里 1 点，共 n 点。
• 额外奖励：每 x 公里触发一次，也就是在走了 x, 2x, 3x …… 公里时会分别奖励 1 点。

因此，额外奖励的次数等于 n 以内有多少个 x 的倍数。

总能量 = 基础能量 (n) + 额外奖励次数。

解题思路

有两种常见的解法：

方法一：循环模拟（适合初学者）

按照题目描述直接模拟每一公里的情况：

• 从第 1 公里走到第 n 公里。
• 每走 1 公里，答案加 1（基础能量）。
• 如果当前公里数是 x 的倍数，答案再加 1（额外奖励）。

这种方法直观易懂，但时间复杂度与 n 成正比。题目中 n 最大为 1000，完全可行。

方法二：公式计算（更高效）

直接计算：

• 基础能量 = n
• 额外奖励次数 = ⌊ n / x ⌋（即 n 除以 x 的整数部分）

总能量 = n + (n / x)

这种方法只需要 O(1) 的时间。

算法说明

参考代码使用的是 方法一 的循环模拟：

cpp
复制
1#include <iostream>
2using namespace std;
3int main() {
4    int t, n, x;
5    if (!(cin >> t)) return 0;
6    while (t--) {
7        cin >> n >> x;
8        int ans = 0;
9        for (int i = 1; i <= n; i++) {
10            ans += 1;          // 基础能量
11            if (i % x == 0) {
12                ans += 1;      // 额外奖励
13            }
14        }
15        cout << ans << endl;
16    }
17    return 0;
18}

代码解释：

1. 首先读入测试数据组数 t。
2. 对于每组数据，读入 n 和 x。
3. 初始化答案 ans 为 0。
4. 使用 for 循环模拟从第 1 公里到第 n 公里：
   • 每次循环 ans 加 1（基础能量）。
   • 使用 if (i % x == 0) 判断当前公里数是否为 x 的整数倍，若是则 ans 再加 1。
5. 循环结束后输出 ans。

如果你掌握了除法运算，也可以将循环替换为更简单的一行公式：

cpp
复制
1cout << n + n / x << endl;

效果完全相同，而且速度更快。

时间复杂度分析

循环模拟方法：

• 对于每组测试数据，循环执行 n 次，每次常数时间操作。
• 每组数据时间复杂度 O(n)。
• 共有 t 组数据，总时间复杂度 O(t × n)。
• 本题数据范围 t ≤ 100, n ≤ 1000，最大计算量为 100 × 1000 = 10^5 次运算，可以在 1 秒内轻松完成。

公式计算方法：

• 每组数据只需一次除法和一次加法，时间复杂度 O(1)。
• 总复杂度 O(t)，非常高效。

两种方法在本题数据规模下都能通过，建议理解循环原理的同时也掌握公式推导，以应对更大数据范围的题目。