c164 - NOIP2015 1.金币

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算在前 K 天裡，騎士一共獲得了多少金幣。金幣的發放方式是，連續 N 天每天發放 N 枚金幣，然後連續 N+1 天每天發放 N+1 枚金幣，以此類推。

解題思路

這題可以使用貪心策略和模擬的方法來解決。我們從第一天開始，按照金幣發放的規則，逐天計算騎士獲得的金幣數量，並將其累加到總和中。每次發放金幣的天數會隨著發放的金幣數量增加，因此需要記錄當前發放的金幣數量以及已經發放的天數。

複雜度分析

• 時間複雜度: O(K)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a;
	while(cin >> a){
		int ans=0;
		for(int j=1,i=1;a>0;j++,a--){
			ans+=i;
			if(i==j){
				i++;
				j=0;
			}
		}
		cout << ans << endl;
	}
}