题解：P5917 [IOI1995] 铺放矩形块
ChampionCyan
·
·
题解
P5917 题解
前言
闲话。
更美观清晰的体验，必看！
双倍经验，题目完全一样，所以与这篇题解内容几乎一样。
思路与做法大纲
这题有 6 种排列方式：
为了接下来的操作，我们先定义一些东西：
/*<==============函数定义==============>*/
inline void init();//输入
inline void part1();//排列方案1
inline void part2();//排列方案2
inline void part3();//排列方案3
inline void part4();//排列方案4
inline void part5();//排列方案5
inline void part6();//排列方案6
inline void update(int, int);//更新答案
inline void do_it();//工作
inline void work(int);//工作
inline void solve();//解答
主函数代码很简单了：
/*<==============主函数==============>*/
int main() {
init();
solve();
return 0;
}
然后我们用之前定义的 mp 判断输入是否重复，这样我们就得到了 update 函数的代码：
inline void update(int length, int width) {
if (length > width)
swap(length, width);
if (length * width > ans || mp.count(make_pair(length, width)) > 0)
return;
/*<================以上情况不用更新！================>*/
//更新
mp.insert(make_pair(length, width));
if (length * width < ans) {
ans = length * width;
res.clear();
mp.insert(make_pair(length, width));
}
res.push_back(make_pair(length, width));
}
再将工作的三个函数框架写出来：
inline void do_it() {
part1();
part2();
part3();
part4();
part5();
part6();
}
inline void work(int depth) {
if (depth == 5) {
do_it();
return;
}
for (int i = 0; i < 4; i++) {
swap(rec[order[i]].length, rec[order[i]].width);//旋转
work(depth + 1);//下一种排列
swap(rec[order[i]].length, rec[order[i]].width);//回溯
work(depth + 1);//下一种排列
}
}
inline void solve() {
do
work(1);
while (next_permutation(order, order + 4));
printf("%d\n", ans);
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i++)
printf("%d %d\n", res[i].first, res[i].second);
}
框架就写好了，然后就是最难的 part1~part6 函数了！
请读者看以下内容时先思考一会儿！
Part1
很简单，画图理解一下，长是和，宽是最短的宽。
```cpp
inline void part1() {
update(rl(0) + rl(1) + rl(2) + rl(3), max(max(rw(0), rw(1)), max(rw(2), rw(3))));
}
```
### Part2
三竖一横。
```cpp
inline void part2() {
update(max(rl(0) + rl(1) + rl(2), rl(3)), max(rw(0), max(rw(1), rw(2))) + rw(3));
}
```
### Part3
有些复杂，但也不难想。
```cpp
inline void part3() {
update(max(rl(0) + rl(1), rl(2)) + rl(3), max(rw(3), max(rw(0), rw(1)) + rw(2)));
}
```
### Part4
两个夹两个。
```cpp
inline void part4() {
update(rl(0) + max(rl(1), rl(2)) + rl(3), max(rw(3), max(rw(0), rw(1) + rw(2))));
}
```
### Part5
与第四种很像，区别在于第四种夹心，第五种两个矩形位于旁边。
```cpp
inline void part5() {
update(max(rl(0), rl(1)) + rl(2) + rl(3), max(max(rw(0) + rw(1), rw(2)), rw(3)));
}
```
### Part6
有点像奥数题，仔细画图想想！
`length` 要分情况讨论，`width` 就是左边两个长的和与右边两个长的和的最小值。
```cpp
inline void part6() {
//比较复杂，慢慢来
int length;
if (rw(2) >= rw(1) + rw(3))
length = max(max(rl(0), rl(1) + rl(2)), rl(2) + rl(3));
else if (rw(3) < rw(2))
length = max(rl(0) + rl(1), max(rl(1), rl(3)) + rl(2));
else if (rw(2) == rw(3))
length = max(rl(0) + rl(1), rl(2) + rl(3));
else if (rw(2) < rw(3) && rw(3) < rw(2) + rw(0))
length = max(rl(0) + rl(1), max(rl(0), rl(2)) + rl(3));
else if (rw(3) >= rw(0) + rw(2))
length = max(rl(1), max(rl(0), rl(2)) + rl(3));
update(length, max(rw(0) + rw(2), rw(1) + rw(3)));
}
```
这样就写完了。
## Code
```cpp
/*<=====头文件，命名空间和宏定义=====>*/
#include <bits/stdc++.h>
#define rl(i) rec[order[i]].length
#define rw(i) rec[order[i]].width
using namespace std;
/*<==============基础定义==============>*/
struct rectangle {
int length, width;
} rec[4];//长方形们
int order[4] = {0, 1, 2, 3};//排列顺序，初始时有序
int ans = 2e9;//答案，初始时设为极大值
set<pair<int, int> > mp;
vector<pair<int, int> > res;
/*<==============函数定义==============>*/
inline void init();//输入
inline void part1();//排列方案1
inline void part2();//排列方案2
inline void part3();//排列方案3
inline void part4();//排列方案4
inline void part5();//排列方案5
inline void part6();//排列方案6
inline void update(int, int);//更新答案
inline void do_it();//工作
inline void work(int);//工作
inline void solve();//解答
/*<==============主函数==============>*/
int main() {
init();
solve();
return 0;
}
inline void init() {
for (int i = 0; i < 4; i++)
scanf("%d%d", &rec[i].length, &rec[i].width);
}
inline void update(int length, int width) {
if (length > width)
swap(length, width);
if (length * width > ans || mp.count(make_pair(length, width)) > 0)
return;
/*<================以上情况不用更新！================>*/
//更新
mp.insert(make_pair(length, width));
if (length * width < ans) {
ans = length * width;
res.clear();
mp.insert(make_pair(length, width));
}
res.push_back(make_pair(length, width));
}
inline void part1() {
update(rl(0) + rl(1) + rl(2) + rl(3), max(max(rw(0), rw(1)), max(rw(2), rw(3))));
}
inline void part2() {
update(max(rl(0) + rl(1) + rl(2), rl(3)), max(rw(0), max(rw(1), rw(2))) + rw(3));
}
inline void part3() {
update(max(rl(0) + rl(1), rl(2)) + rl(3), max(rw(3), max(rw(0), rw(1)) + rw(2)));
}
inline void part4() {
update(rl(0) + max(rl(1), rl(2)) + rl(3), max(rw(3), max(rw(0), rw(1) + rw(2))));
}
inline void part5() {
update(max(rl(0), rl(1)) + rl(2) + rl(3), max(max(rw(0) + rw(1), rw(2)), rw(3)));
}
inline void part6() {
//比较复杂，慢慢来
int length;
if (rw(2) >= rw(1) + rw(3))
length = max(max(rl(0), rl(1) + rl(2)), rl(2) + rl(3));
else if (rw(3) < rw(2))
length = max(rl(0) + rl(1), max(rl(1), rl(3)) + rl(2));
else if (rw(2) == rw(3))
length = max(rl(0) + rl(1), rl(2) + rl(3));
else if (rw(2) < rw(3) && rw(3) < rw(2) + rw(0))
length = max(rl(0) + rl(1), max(rl(0), rl(2)) + rl(3));
else if (rw(3) >= rw(0) + rw(2))
length = max(rl(1), max(rl(0), rl(2)) + rl(3));
update(length, max(rw(0) + rw(2), rw(1) + rw(3)));
}
inline void do_it() {
part1();
part2();
part3();
part4();
part5();
part6();
}
inline void work(int depth) {
if (depth == 5) {
do_it();
return;
}
for (int i = 0; i < 4; i++) {
swap(rec[order[i]].length, rec[order[i]].width);//旋转
work(depth + 1);//下一种排列
swap(rec[order[i]].length, rec[order[i]].width);//回溯
work(depth + 1);//下一种排列
}
}
inline void solve() {
do
work(1);
while (next_permutation(order, order + 4));
printf("%d\n", ans);
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); i++)
printf("%d %d\n", res[i].first, res[i].second);
}
```