8061 【15NOIP普及组】金币
大约 1 分钟
8061 【15NOIP普及组】金币
【算法】 模拟、枚举
【C++】 循环
【难度】 入门
一、题目简述
国王发金币的规则:
- 第 1 天:1 枚(连续 1 天)
- 第 2~3 天:每天 2 枚(连续 2 天)
- 第 4~6 天:每天 3 枚(连续 3 天)
- 第 7~10 天:每天 4 枚(连续 4 天)
- ...
给定天数 ,求前 天一共获得多少金币。
二、解题思路
模拟每天的发放过程。用变量:
day:当前是第几天coin:当前每天发多少金币cnt:当前金币数已经连续发了几天total:总金币数
每天累加 coin 到 total,同时 cnt++。当 cnt == coin 时,说明这个阶段结束了,coin++ 且 cnt 归零。
手动模拟 :
- 第1天:coin=1, total=1
- 第2天:coin=2, total=3
- 第3天:coin=2, total=5
- 第4天:coin=3, total=8
- 第5天:coin=3, total=11
- 第6天:coin=3, total=14
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int K;
cin >> K;
int total = 0;
int coin = 1; // 当前每天发的金币数
int cnt = 0; // 当前金币数已连续发了几天
for (int day = 1; day <= K; day++) {
total += coin;
cnt++;
if (cnt == coin) { // 该阶段结束
coin++;
cnt = 0;
}
}
cout << total << endl;
return 0;
}四、复杂度分析
- 时间:, 最大约在 级别(题目未明确给出,但模拟足够快)。
- 空间:。
