a267 - 太空梭的油箱

🔗 前往 ZeroJudge 原題

題目描述

題目描述了太空梭的燃料問題。太空梭和油箱都有燃料容量限制，且每月都會消耗燃料。油箱本身也會消耗燃料，因此可以丟棄空的油箱以減少每月耗油量。目標是計算在給定油箱數量 N 的情況下，太空梭最多能航行多少個月。

解題思路

這題的核心在於模擬太空梭的燃料消耗過程。由於油箱本身也會消耗燃料，因此當油箱變空時，丟棄油箱是最佳策略。程式碼預先計算了不同油箱數量下的最大航行月份數，並將結果儲存在 arr 陣列中。然後，程式讀取輸入的油箱數量 N，並從 arr 陣列中輸出對應的結果。預計算的目的是為了避免在每次輸入時都進行模擬計算，提高效率。

複雜度分析

• 時間複雜度: O(N + M)，其中 N 是預計算陣列的大小 (500001)，M 是輸入的測資數量。預計算陣列需要 O(N) 的時間，處理每個輸入需要 O(1) 的時間。
• 空間複雜度: O(N)，主要用於儲存預計算結果的 arr 陣列。

程式碼

#include <iostream>
using namespace std;
int arr[500001],n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	for(int i(0);i<=500000;++i){
		int day(0),all(5+i*5),co(1+i);
		while(all>0){
			++day;
			all-=co;
			co=all/5;
			if(all%5)++co;
		}
		arr[i]=day;
	}
	while(cin >> n){
		if(n==-1)break;
		else cout << arr[n] << "\n";
	}
}