[NOIP 2015 普及组] 金币

知识点

模拟、分段计数

解题思路

第x轮连续x天每天得到x枚金币。按轮模拟，每轮实际领取天数为min(剩余天数,x)，累加后减少剩余天数。

正确性说明

每轮完全对应题目连续同额金币的一个时间段；最后不足一轮时只计入所需的剩余天数，因此所有前k天各计算一次。

易错点

最后一轮不一定完整，不能一律加x*x；天数用剩余量可避免多算一天。

复杂度

轮数为O(sqrt(k))，时间O(sqrt(k))，空间O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long left,ans=0;cin>>left;
    for(long long x=1;left>0;++x){long long days=min(left,x);ans+=days*x;left-=days;}
    cout<<ans<<'\n';
}