[noip2015-普及] 金币

题目描述

国王把金币作为工资发给骑士：第一天收到 $1$ 枚金币；之后连续 $2$ 天每天收到 $2$ 枚；再之后连续 $3$ 天每天收到 $3$ 枚……当连续 $N$ 天每天收到 $N$ 枚金币后，接着连续 $N+1$ 天每天收到 $N+1$ 枚。请计算前 $K$ 天里骑士一共获得多少金币。 输入格式： 一个正整数 $K$ ，表示发放金币的天数（ $1 \le K \le 10{,}000$ ）。 输出格式： 一个正整数，即骑士收到的金币总数。样例 1：输入 6，输出 14（ $1+2+2+3+3+3$ ）；样例 2：输入 1000，输出 29820。

思路

工资按“段”变化：第 $N$ 段是连续 $N$ 天、每天 $N$ 枚金币，所以段内 $N$ 天累加等价于一次加上 $N \times N$ 。用 left 记录还没算的天数，每轮取 days = min(wage, left) 天、累加 days * wage 并扣减 left，left 为 0 即结束——末段不够一整段时被自动截断。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 11:07
# update_at: 2026-10-02 11:07

import sys
from itertools import count


def total_coins(days_total: int) -> int:
    """按“连续 N 天、每天 N 枚”分段累加，返回前 days_total 天的金币总数。"""
    total = 0          # 已确认的金币累计
    left = days_total  # 还没被分段覆盖的天数
    for wage in count(1):          # 第 N 段：每天 wage 枚，共 wage 天
        days = min(wage, left)     # 最后一段可能被 days_total 截断
        total += days * wage
        left -= days
        if left == 0:              # 所有天数都被分段覆盖
            break
    return total


def solve() -> None:
    days_total = int(sys.stdin.buffer.read())
    print(total_coins(days_total))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 15:25
 * update_at: 2026-10-06 15:25
 */

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

// 按段发放金币：第 wage 段是连续 wage 天、每天 wage 枚
// O(√K)：前 N 段共 N(N+1)/2 天，1e4 天只需约 141 段
int main() {
    ll k;                 // 要统计的天数
    ll left;              // 还没计入答案的剩余天数
    ll wage = 1;          // 当前段号，也是本段每天的金币数
    ll total = 0;         // 累计金币数

    scanf("%lld", &k);
    left = k;

    while (left > 0) {
        // 本段实际计入的天数：够一整段取整段，不够就取完剩余天数
        ll days = min(wage, left);
        total += days * wage; // 段内每天都是 wage 枚，N 次加法合并成一次乘法
        left -= days;
        wage++;
    }

    printf("%lld\n", total);
    return 0;
}

[noip2015-普及] 金币

目录

题目描述

思路

参考代码