当前位置:首页 > 模拟 > 正文
SSOJ1408金币(NOIP2015)
628+

题目大意:国王给骑士发金币,N天金币之和为N个数相加,规律如下:1+2+2+3+3+3+4+4+…,骑士N天可得多少金币?

题目描述

国王将金币作为工资,发放给忠诚的骑士。 第一天骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天,每天收到四枚金币,以此类推;这种工资发放模式会一直延续下去,当连续N天收到N枚金币后,骑士会在之后的N+1天,每天收到N+1枚金币。 请计算前K天里,骑士一共获得了多少金币。

输入

输入包含一个正整数K,表示发放金币的天数。

输出

输出一个正整数,即骑士收到的金币数。

样例输入

样例一:6
样例二:1000

样例输出

样例一:14
样例二:29820

提示

对于全部数据,1≤K≤10000

对于样例一,骑士一共收到1+2+2+3+3+3=14枚金币。

NOIP2015普及组第一题

解题思路

根据题目意思,计算1+2+2+3+3+3+4+4+…的和,共N项,可以逐项相加,也可以金币相同的一起加,还可以用平方和公式直接计算。

程序实现

逐项相加,时间复杂度O(N)。共加N次,工资为m个金币的需要加m天,变量s记录金币和,变量c记录金币为m的加了多少天。如果c==m,那么下一次金币为m+1,金币m+1还没加,c=0。

金币数量相同的工资一起加,即1^2+2^2+3^+…,时间复杂度O(√N)。一共需要加n天工资,每次加m*m,即加了m天,加完后n减去m,直到n不大于0工资才加完了。最终n可能是负数,负数表示最后多加了几天的工资,减回去就行。

1^2+2^2+3^2+…n^2是可以用公式计算的,1+2+3+…+n约等于N,n*(n+1)/2约等于N,n约等于√N。先计算出大概的n,然后用公式求出平方和。sqrt返回的浮点数赋值给整数,向下取整,可能会让n变小,又或者最后的工资n不足n天,也有可能导致n变小,最后计算一下还差多少天没加,把最后那几天的工资(n+1)补加回来就行。

注意:最后的工资n+1不足n+1天,可能会导致求出来的是n+1,造成多加的情况,为了避免最后判断多加还是少加,最后的工资是n还是n+1,我们可以统一一下最后都是补工资,即计算完n后,如果n*(n+1)/2>N,那么n减1,避免多加的情况出现。

更多

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ1408金币(NOIP2015):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter