k513 - P1.停車場 (Parking)
題目描述
題目描述一個停車場有三種大小的車位，以及抵達的車輛數量。車輛依序停入車位，目標是計算停滿所有車輛後，停了多少輛車。車輛會優先停入較小的車位，如果較小的車位已滿，則停入較大的車位。
解題思路
這題的解題思路是貪婪演算法。首先，將車輛按照大小分類，然後按照車位大小的順序，將車輛停入車位。如果某種大小的車位已滿，則將車輛停入更大的車位。由於題目要求計算停了多少輛車，因此需要記錄每種大小的車位還剩多少空間。程式碼中，a 陣列表示每種大小車位的數量，b 陣列表示每種大小車輛的數量。程式碼使用兩個巢狀迴圈，外層迴圈遍歷車位大小，內層迴圈遍歷車位種類。在內層迴圈中，比較車輛數量和車位數量，將車輛停入車位，並更新車輛數量和車位數量。
複雜度分析
- 時間複雜度: O(1)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int a[3],b[3],n,x,ans;
int main(){
for(int i=0;i<3;++i){
cin >> a[i];
}
cin >> n;
for(int i=0;i<n;++i){
cin >> x;
if(x<200)++b[0];
else if(x>=500)++b[2];
else ++b[1];
}
for(int i=0;i<3;++i){
for(int j=i;j<3;++j){
if(b[i]>=a[j]){
ans+=a[j];
b[i]-=a[j];
a[j]=0;
}
else{
ans+=b[i];
a[j]-=b[i];
b[i]=0;
}
}
}
cout << ans;
}