题解 | #[NOIP2015]金币#

#include <stdio.h>

//思路：
//由题：将天数按照每天的金币数量分组：1天（1金币） 2天（2金币） 3天（3金币）... n天（n金币）
//k是发放金币的总天数
//因此可以根据此分组规律找到k的范围 即在第k天时发放多少枚金币：
//1+2+3+...+n < k <= 1+2+3+...+n+(n+1) （在第k天发放（n+1）枚金币）
//那么骑士收到的金币即为：total=1*1+2*2+3*3+...+ n*n + (n+1)*{k-(1+2+3+...+n)}
//* {k-(1+2+3+...+n)}为发放（n+1）枚金币的天数

//由此思路：

int main()
{
    int k = 0;//总天数
    scanf("%d", &k);
    int sum1 = 0, sum2 = 0;
    int i = 0;//天数分组
    int j = 0;
    for (i = 1; sum1 <= k; i++)
    {
        sum1 += i;
    }//sum1即为1+2+3+...+n+（n+1）
    i -= 1;//for循环会在我们需要的（n+1）上多运行一次n++ 因此需要-1
    sum1 -= i;//得到1+2+3+...+n的值
    for (j = 0; j < i; j++)
    {
        sum2 += j * j;
    }
    sum2 += (k - sum1) * i;
    printf("%d", sum2);
    return 0;
}