b944 - 好想上廁所(男廁篇)
題目描述
題目描述了男生使用廁所的習慣，他們會盡量選擇相隔一個小便斗，如果找不到則使用相鄰的。程式需要模擬這個過程，並輸出每個小便斗的使用者編號和剩餘時間。
解題思路
這題的核心是模擬廁所的使用情況。程式使用一個陣列 a[25][2] 來記錄每個小便斗的使用者編號 (a[i][0]) 和剩餘時間 (a[i][1])。對於每個新來的男生，程式會從小便斗 1 開始尋找空閒的。優先選擇相隔一個小便斗的空位，如果找不到，則選擇相鄰的空位。如果所有小便斗都已滿，則輸出 "Not enough"。每次找到空位後，更新小便斗的使用者編號和剩餘時間，並減少已使用小便斗的剩餘時間。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是小便斗的數量。在最壞情況下，程式需要遍歷所有小便斗來尋找空位。
- 空間複雜度: O(n)，程式使用一個大小為 n 的陣列來儲存小便斗的資訊。
程式碼
#include <iostream>
using namespace std;
int a[25][2],n,b,t;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
while(cin >> b >> t){
for(int i=1;i<=n;++i){
if(a[i][0]){
a[i][1]--;
if(a[i][1]<=0){
a[i][0]=a[i][1]=0;
}
}
}
int ac=1;
for(int i=1;i<=n&∾++i){
if(a[i][0]==0&&a[i-1][0]==0&&a[i+1][0]==0){
ac=0;
a[i][0]=b;
a[i][1]=t;
}
}
for(int i=1;i<=n&∾++i){
if(a[i][0]==0){
ac=0;
a[i][0]=b;
a[i][1]=t;
}
}
if(ac){
cout << " Not enough\n";
}
cout << "Number: ";
for(int i=1;i<=n;++i){
cout << a[i][0] << " ";
}
cout << "\n Time: ";
for(int i=1;i<=n;++i){
cout << a[i][1] << " ";
}
cout << "\n";
}
}