g420 - PB.BAD question
題目描述
題目描述了菜雞蛋玩東方project遊戲的情況。給定初始生命值、每一關的生命損失和每一關結束後的生命獎勵，要求計算菜雞蛋最多能通過多少關，前提是生命值不能變為負數。
解題思路
這題可以使用貪心策略，模擬遊戲過程。從第一關開始，依次扣除生命值，如果生命值不為負數，則獲得獎勵。重複此過程，直到生命值變為負數或到達最後一關。記錄通過的關卡數，即為答案。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
long long ans,n,m,a[1000005],x;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1;i<=n;++i){
cin >> a[i];
}
for(int i=1;i<=n&&m>=0;++i){
++ans;
m-=a[i];
if(m<0)break;
cin >> x;
m+=x;
}
cout << ans;
}