复赛一：金币

洛谷：P2669
OJ：P4946

用模拟算法即可，打卡题。

解题思路：

这个问题要求计算骑士在前 k 天内一共获得的金币数。根据题目描述，金币的发放遵循以下规律：

  • 第 1 阶段：持续 1 天，每天获得 1 枚金币。
  • 第 2 阶段：持续 2 天，每天获得 2 枚金币。
  • 第 3 阶段：持续 3 天，每天获得 3 枚金币。
  • …
  • 第 n 阶段：持续 n 天，每天获得 n 枚金币。

我们的目标是模拟这一发放过程，并在总天数不超过 k 的情况下，计算累计的金币总数。

具体思路：

  1. 初始化变量：
  • k：总天数，用户输入。
  • s：累计金币数，初始为 0。
  • t：已计算的天数，初始为 0。
  • i：当前阶段的编号，从 1 开始，每个阶段的天数和每天获得的金币数都等于 i。
  1. 循环计算：
  • 使用 while (t < k) 循环，表示只要已计算的天数还未达到总天数，就继续计算。
  • 在每个阶段，计算实际需要计算的天数 days，该值为当前阶段的天数 i 和剩余天数 k - t 中的较小值，避免超过总天数。
    • int days = min(i, k - t);
  • 计算当前阶段的金币总数，并累加到 s 中：
    • s += days * i;
  • 更新已计算的天数：
    • t += days;
  • 阶段编号递增，进入下一个阶段：
    • i++;
  1. 输出结果：
  • 当已计算的天数达到或超过总天数时，循环结束。
  • 输出累计的金币总数 s。

算法优势：

  • 效率高： 通过按阶段计算，避免了逐天累加，减少了循环次数，提高了程序效率。
  • 代码简洁： 使用 min 函数处理可能的部分阶段，逻辑清晰，代码简洁。
  • 易于理解： 变量命名和注释明确，方便阅读和维护。

示例演示：

假设输入 k = 6。

  • 阶段 1：
  • i = 1
  • days = min(1, 6 - 0) = 1
  • s += 1 * 1 = 1（累计金币数为 1）
  • t += 1 = 1
  • 阶段 2：
  • i = 2
  • days = min(2, 6 - 1) = 2
  • s += 2 * 2 = 4（累计金币数为 1 + 4 = 5）
  • t += 2 = 3
  • 阶段 3：
  • i = 3
  • days = min(3, 6 - 3) = 3
  • s += 3 * 3 = 9（累计金币数为 5 + 9 = 14）
  • t += 3 = 6
  • 循环结束：
  • 因为 t = 6，已达到总天数 k = 6，循环结束。
  • 输出结果：
  • s = 14，即骑士在 6 天内共获得 14 枚金币。

结论：

该算法通过逐阶段计算，在每个阶段内直接计算获得的金币总数，避免了不必要的计算。使用 min 函数确保计算的天数不会超过总天数 k，逻辑严谨，效率高，适用于大数据量的情况。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**************************************************************** 
 * Description: 2015_J_1  coin
 * Author: Alex Li
 * Date: 2024-09-18 14:24:45
 * LastEditTime: 2024-09-18 14:39:52
****************************************************************/
#include <iostream>
using namespace std;

int main(){
    int k, s = 0, t = 0;
    cin >> k;

    int i = 1; // 当前阶段的金币数和天数
    while (t < k) {
        int days = min(i, k - t); // 计算当前阶段的天数，防止超过总天数
        s += days * i;            // 累加当前阶段获得的金币数
        t += days;                // 更新已计算的天数
        i++;                      // 进入下一个阶段
    }
    cout << s << endl; // 输出总金币数
    return 0;
}
Previous Topic
Back to Lesson
Next Topic