e534 - 01587 - Box
題目描述
題目給定六個矩形木板的寬度和高度，判斷是否能用這些木板組合成一個長方體盒子。
解題思路
解題思路是先對六個木板按照寬度進行排序，然後檢查是否滿足以下條件：
- 相鄰的兩個木板寬度和高度必須相同。
- 檢查是否存在三組相同的木板，可以組成長方體的六個面。具體來說，需要檢查是否存在兩種不同的寬高組合，且每種組合有三塊木板。
程式碼首先讀取六個木板的寬度和高度，然後將寬度和高度進行排序。接著，程式碼檢查相鄰的兩個木板是否具有相同的寬度和高度。如果沒有，則輸出 "IMPOSSIBLE"。如果相鄰的木板寬度和高度相同，則程式碼檢查是否存在三組相同的木板，可以組成長方體的六個面。如果存在，則輸出 "POSSIBLE"，否則輸出 "IMPOSSIBLE"。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是木板的數量 (本題為 6)。主要來自排序操作。
- 空間複雜度: O(n)，主要來自儲存木板寬度和高度的陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int a[6][2];
int main() {
cin.sync_with_stdio(false), cin.tie(nullptr);
while(cin >> a[0][0] >> a[0][1]){
int ac=1,ac2=0;
for(int i=1;i<6;++i){
cin >> a[i][0] >> a[i][1];
}
for(int i=0;i<6;++i){
if(a[i][0]>a[i][1]){
swap(a[i][0],a[i][1]);
}
}
for(int i=0;i<6;++i){
for(int j=i+1;j<6;++j){
if(a[i][0]<a[j][0]||(a[i][0]==a[j][0]&&a[i][1]<a[j][1])){
swap(a[i][0],a[j][0]);
swap(a[i][1],a[j][1]);
}
}
}
for(int i=0;i<6;i+=2){
if(a[i][0]!=a[i+1][0]||a[i][1]!=a[i+1][1]){
ac=0;
}
}
int k[6]={a[0][0],a[0][1],a[2][0],a[2][1],a[4][0],a[4][1]};
if(k[0]==k[2]){
if(k[1]==k[4]&&k[3]==k[5]){
ac2=1;
}
else if(k[1]==k[5]&&k[3]==k[4]){
ac2=1;
}
}
if(k[0]==k[3]){
if(k[1]==k[4]&&k[2]==k[5]){
ac2=1;
}
else if(k[1]==k[5]&&k[2]==k[4]){
ac2=1;
}
}
if(k[0]==k[4]){
if(k[1]==k[2]&&k[3]==k[5]){
ac2=1;
}
else if(k[1]==k[3]&&k[2]==k[5]){
ac2=1;
}
}
if(k[0]==k[5]){
if(k[1]==k[3]&&k[2]==k[4]){
ac2=1;
}
else if(k[1]==k[2]&&k[3]==k[4]){
ac2=1;
}
}
if(ac==0||ac2==0){
cout << "IMPOSSIBLE\n";
}
else{
cout << "POSSIBLE\n";
}
}
}