金币 - 题目列表

题意

第 $i$ 个发薪阶段持续 $i$ 天，每天发 $i$ 枚金币。求前给定天数内收到的金币总数。

思路

变量 salary 同时表示本阶段每天的金币数和本阶段长度。当前剩余天数可能不足一个完整阶段，因此本阶段实际发放天数为 min(days, salary)。

加入 salary * paid_days 后扣除已处理天数，并进入下一阶段。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11days = int(input())
total = 0
salary = 1

while days > 0:
    paid_days = min(days, salary)
    total += salary * paid_days
    days -= paid_days
    salary += 1

print(total)

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/* 
 *
 *  1
 *  2 3
 *  4 5 6
 *  7 8 9 10
 *  11 12 13 14 15
 * */
#include <cstdio>

int main(){
    int sum = 0;
    int n;
    scanf("%d",&n);
    int i,j,idx=0;
    for (i=1;1;i++){
       for(j=1;j<=i;j++){
           sum += i;
           idx++;
           if( idx == n){
               printf("%d\n",sum);
               return 0;
           }
       }
    }
    return 0;
}

复杂度

处理到第 $k$ 个阶段时已覆盖约 $k^2/2$ 天，故时间复杂度为 $O(\sqrt n)$ ，额外空间复杂度为 $O(1)$ 。

总结

按规则天然分段的模拟题，直接处理整段比逐天累加更容易表达边界。

金币

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结