j178 - 手遊廣告 (Advertisement)

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個手遊廣告的獎勵機制。一開始玩家擁有 a 點金幣，接著會看到 m 個廣告。每個廣告會給予玩家 x 點金幣。如果玩家的金幣數量在任何時候達到或超過了 a 的初始值，則輸出初始值 a 並結束程式。如果看完所有廣告後，玩家的金幣數量仍然小於初始值 a，則輸出最終的金幣數量。

解題思路

這題的解題思路是模擬廣告獎勵的過程。我們初始化金幣數量為 a，然後遍歷每個廣告，每次廣告看完後，將獎勵 x 加到金幣數量中。在每次加獎勵後，檢查金幣數量是否達到或超過了初始值 a。如果達到或超過，則輸出 a 並結束程式。如果遍歷完所有廣告後，金幣數量仍然小於 a，則輸出最終的金幣數量。這是一個簡單的貪心模擬過程。

複雜度分析

• 時間複雜度: O(m)，其中 m 是廣告的數量。因為我們需要遍歷所有廣告。
• 空間複雜度: O(1)，因為我們只使用了幾個常數大小的變數。

程式碼

#include <iostream>
using namespace std;
int m,a,x;
int main(){
	cin >> m >> a;
	for(int i=0;i<m;++i){
		cin >> x;
		if(x>=a){
			cout << a;
			return 0;
		} 
		a+=x;
	}
	cout << a;
	return 0;
}