e549 - 00737 - Gleaming the Cubes
題目描述
題目要求計算多個立方體重疊部分的體積。輸入包含立方體的數量 n，以及每個立方體的坐標和邊長。需要計算所有立方體共同擁有的體積。
解題思路
這題的核心思想是分別計算在 x, y, z 三個軸上的重疊區間長度，然後將這三個長度相乘即可得到重疊體積。程式碼使用貪心策略，維護每個軸上重疊區間的最大最小值。對於每個立方體，更新 x, y, z 三個軸上的最大最小值。最後，計算每個軸上重疊區間的長度，並將它們相乘。如果計算出的重疊體積為負數，則輸出 0。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,a[6],b[4];
while(cin >> n){
if(n==0)break;
for(int i=0;i<n;++i){
for(int j=0;j<4;++j){
cin >> b[j];
}
for(int j=0;j<3;++j){
if(i){
a[j*2]=max(a[j*2],b[j]);
a[j*2+1]=min(a[j*2+1],b[j]+b[3]);
}
else{
a[j*2]=b[j];
a[j*2+1]=b[j]+b[3];
}
}
}
int k=1;
for(int i=0;i<3;++i){
k*=(a[i*2+1]-a[i*2]);
}
cout << max(0,k) << "\n";
}
}