P4915 金币（入门）

解题思路

第一步，理解题意。 国王发工资的规则是：第1天发1枚金币；接下来连续2天每天发2枚；再接下来连续3天每天发3枚；再接下来连续4天每天发4枚……每天发的金币数按段递增，每一段的长度正好等于每天发的金币数。问前k天一共发了多少枚金币。

第二步，按段模拟。 用一个变量day表示当前这一段每天发几枚金币，用一个变量cnt记录已经过了多少天。每过一天，就给总数sum加上day枚金币，同时cnt加1。当这一段的day天过完以后，day加1，进入下一段。

第三步，注意循环停止条件。 我们要的是前k天，所以即使当前这一段还没过完，只要天数cnt已经达到k就立刻停止。代码里用for循环让i从0到day-1，同时判断cnt小于k才继续。

第四步，举例子。 样例k=6：第1天发1枚；第2、3天每天发2枚，共4枚；第4、5、6天每天发3枚，共9枚。总数1+2+2+3+3+3=14，输出14，和样例一致。

第五步，数据范围。 k最大是10000，金币总数大约是1+2+3+…+10000等于5000万枚左右，用int可能不够保险，所以用long long存储总和sum。这个题直接按题意一步步模拟就可以了。

参考代码

// 金币：按段模拟，第day段每天发day枚金币，连续发day天
#include <iostream>
using namespace std;
int main() {
    int k;
    cin >> k;
    long long sum = 0;
    int day = 1; // 当前每天发几枚金币
    int cnt = 0; // 已经过了多少天
    while (cnt < k) {
        for (int i = 0; i < day && cnt < k; i++) {
            sum += day;
            cnt++;
        }
        day++;
    }
    cout << sum << endl;
    return 0;
}

复杂度分析

循环次数正好是k次，所以时间复杂度是O(k)。k最大10000，运行速度非常快。空间上只用了几个变量，空间复杂度O(1)。这个题目数据范围小，直接模拟是最简单也最不容易出错的做法。