SP11573 题解-mnesia

mnesia · 2021-07-31 17:52:07 · 题解

这道题需要一定的思维量，但是最后代码的实现是比较简单的。

题目给出四个正方形的边长，要求找到最小的大正方形，使得其能不重叠地容纳下这四个正方形（平铺）。

我的推导过程如下：假设这四个正方形的边长从小到大依次为 a_1，a_2，a_3，a_4。首先很容易想到，只要 3 号及 4 号正方形被排布好，大正方形的边长就已经确定，剩下的两个正方形就一定能塞进剩余的空隙中。

接下来简单证明一下本题结论：输出 a_3 + a_4 的值。

首先假设 4 号正方形被放在大正方形左上角。此时 3 号正方形有三种选择：放在右上角、左下角、右下角。放在右上角和左下角时，很容易看出大正方形的边长已经确定，即 a_3 + a_4；而放在右下角时，可知无论 3 号矩形如何移动，其必有一条边对应到大正方形上长度为 a_3。因此，大正方形的边长为 a_3 + a_4。从而得证。

可以借助下面这张图片来理解一下 3 号矩形放在右下角时的情况：

下面给出代码：

#include<iostream>
#include<algorithm>
using namespace std;
int a[5];
int cnt = 1;
int main()
{
    while(cin >> a[1] >> a[2] >> a[3] >> a[4])
    {
        sort(a + 1, a + 5, greater<int>());
        cout << "Case " << cnt << ": " << a[1] + a[2] << endl;
        cnt++;
    }
    return 0;
}

注意使用 greater<int> 时后面一定要加一个括号，否则会引发编译错误。当然，也可以直接默认从小到大排序，输出 a[3] + a[4]。