题解：P14601 [NWRRC 2025] Bounding Boxes

Solil1019 · 2025-11-27 16:58:43 · 题解

题目大意

给定 n 个长方体包装盒的尺寸，需要找到一个长方体纪念品盒子，使得这个纪念品盒子能够放入所有包装盒中（可以旋转，但各边必须平行），求纪念品盒子的最大可能体积。

解法

对于每个包装盒：

1. 将其三个尺寸从小到大排序；
2. 这样得到的三元组 (a_i, b_i, c_i) 表示：
   • 能放入该盒子的纪念品盒子的最小边最多为 a_i。
   • 中间边最多为 b_i。
   • 最大边最多为 c_i。

对于所有包装盒：

1. 取所有最小边的最小值：A = \min(a_i)。
2. 取所有中间边的最小值：B = \min(b_i)。
3. 取所有最大边的最小值：C = \min(c_i)。

最终答案就是 A \times B \times C。

为什么这样可行？

• 因为对于任意包装盒，排序后的三个尺寸分别对应了能放入该盒子的纪念品盒子的三个尺寸的上限。
• 取所有包装盒对应位置的最小值，就保证了纪念品盒子能放入所有包装盒。

Code

#include <bits/stdc++.h>
using namespace std;
int n,v[3],a,b,c;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    a=b=c=INT_MAX;//赋值为极大值
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[0]>>v[1]>>v[2];
        sort(v+0,v+3);
        a=min(a,v[0]);
        b=min(b,v[1]);
        c=min(c,v[2]);
    }
    cout<<a*b*c;
}