国王将金币作为工资，发放给忠诚的骑士。 问题 G: 金币

题目描述
国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1天里，每天收到N+1枚金币。

请计算在前K天里，骑士一共获得了多少金币。
输入
输入只有1行，包含一个正整数K(1≤K≤10000)，表示发放金币的天数。
输出
输出只有1行，包含一个正整数，即骑士收到的金币数。
样例输入
6
样例输出
14
提示
骑士第一天收到一枚金币；第二天和第三天，每天收到两枚金币；第四、五、六天，每天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。

代码看着很简单，但是想了快十分钟。

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

int main()	{
	int i,j,sum=0,sumd=0,n,ans;
	scanf("%d",&n);
	for (i=1;;i++)	{
		sum+=i;
		if (sum>=n)	break;
	}
	i--;
	for (j=1;j<=i;j++)
		sumd+=j*j;
	ans=(1+i)*(n-(sum-i-1))+sumd;
	printf("%d\n",ans);
	return 0;
}

这是去年写的，只是贴了个代码，在这里解释一下。

定义“n完整递增”为连续的1个1，2个2，。。。，n个n的序列。例如，1,2,2是完整递增，1,2,2,3,3,3是完整递增，但1,2,以及1,2,2,3,3就不是完整递增。

题目中金币数可以分为两部分，就是前面的k完整递增，这是a部分，设其中size(a)个元素；以及后面的n-size(a)个相同的数字，均为k+1，这是b部分。求出a部分和b部分的和相加，就是答案。设a部分的和为sum(a)，显然b部分的和sum(b)为(n-size(a))(k+1).

代码中的sum，可以视作上面的k完整递增序列中的数字个数。求sum=1+2+…+i,如果sum大于了n，则i加过头了1位，则i- -，则此时的i就是上面的k。

举个例子，输入8，则金币序列为1,2,2,3,3,3,4,4,则i为3，size(a)=6.

观察到k完整递增序列的和，可以简单地用1^2 + 2^2 + 3^2 +4^2 + … + k^2求得，则代码中的sumd即为i完整递增序列的元素和，就是sum(a)=sumd.

又由最初知，sum(b)=(n-size(a))*(k+1)，此处k即现在i。但是注意，虽然之前i- -了，但是那是由于sum已经大于或者等于n了。此时sum仍未减去超过的部分。所以size(a)=sum-(i+1)。i+1,是因为当时sum加的数（也就是使sum大于等于n的数），比现在已经i- -的i要大1.

那么最后一个ans就解释清楚了，两个部分和sum(a)+sum(b)就行了。

现在看来这个题根本没必要想这么多，直接模拟就行了。下面是代码，简洁易懂，不注释了。

#include <bits/stdc++.h>
using namespace std;

int main()	{
	int n,sum=0,cnt=0;
	cin>>n;
	for (int i=1;i<=n;i++)	{
		for (int j=0;j<i;j++)	{
			sum+=i;
			cnt++;
			if (cnt==n) break;
		}
		if (cnt==n)	break;
	}
	cout<<sum<<endl;
	return 0;
}