a270 - 爬樓梯有益身心健康

🔗 前往 ZeroJudge 原題

題目描述

題目描述了康康小學的樓層高度不一，需要檢查老師在八節課之間移動樓層是否能在下課時間內完成。輸入包含下課時間長度、每層樓梯所需時間以及老師每節課的教室樓層，輸出判斷老師是否能準時到達每節課。

解題思路

這題的核心是模擬老師移動樓層的過程，並判斷每次移動是否能在允許的時間內完成。程式首先讀取下課時間、每層樓梯所需時間以及老師的課表。然後，迭代老師的課表，計算從上一節課的樓層到下一節課的樓層所需的時間，並與剩餘時間進行比較。如果任何一次移動所需時間超過剩餘時間，則輸出 "no"，否則輸出 "yes"。程式使用一個迴圈來遍歷老師的課表，並在迴圈內部計算移動時間。

複雜度分析

• 時間複雜度: O(n)，其中 n 是課表的長度 (在本題中為 8)。迴圈迭代 8 次，每次迭代的計算量是常數級別。
• 空間複雜度: O(1)。程式只使用了幾個整數變數來存儲數據，空間使用量是固定的，不隨輸入大小變化。

程式碼

#include <iostream>
using namespace std;
int main(){
	int t,l[4],c,x;
	while(cin >> t){
		bool ans=0;
		cin >> l[0] >> l[1] >> l[2] >> l[3];
		cin >> c;
		x=c;
		for(int i=0;i<7;++i){
			cin >> c;
			if(x==c)continue;
			int tmp=0;
			for(int p=min(x,c)-1,q=max(x,c)-1;p<q;++p)
				tmp+=l[p];
			if(tmp>t)
				ans=1;
			x=c;
		}
		(ans)?cout << "no\n":cout << "yes\n";
	}
}