🔍 解题思路

题意是给你四个矩形，按题目给的六种排法，找出能容纳的下四个矩形的最小矩形面积，并将所求的最小矩形边 按小边 从小到大的顺序输出。

看到这题完全没有思路，网上看大神们的解析，有说到用深搜，但是不知道这题怎么用深搜，大概是自己没有理解 深搜 的用法。

于是选用了令一种思路，枚举。

因为题目中只说了六种情况，所以将他们全表示出来，加上四个矩形的位置及长宽变化，一一枚举。

最后对答案进行排序，即可。

/*
  ID: who jay
  LANG: C++
  TASK: packrec
 */
#include <iostream>
#include <vector>
using namespace std;


void quickSort(vector<int> &s, int l, int r)
{
	if (l< r)
	{
		int i = l, j = r, x = s[l];
		while (i < j)
		{
			while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
				j--;
			if(i < j)
				s[i++] = s[j];
			while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
				i++;
			if(i < j)
				s[j--] = s[i];
		}
		s[i] = x;
		quickSort(s, l, i - 1); // 递归调用
		quickSort(s, i + 1, r);
	}
}

int perm[24][4] = {{1,2,3,4}, {1,2,4,3}, {1,3,2,4}, {1,3,4,2},
	{1,4,2,3}, {1,4,3,2}, {2,1,3,4}, {2,1,4,3},
	{2,3,1,4}, {2,3,4,1}, {2,4,1,3}, {2,4,3,1},
	{3,1,2,4}, {3,1,4,2}, {3,2,1,4}, {3,2,4,1},
	{3,4,1,2}, {3,4,2,1}, {4,1,2,3}, {4,1,3,2},
	{4,2,1,3}, {4,2,3,1}, {4,3,1,2}, {4,3,2,1}};

int lw[2][2] = {{0,1},{1,0}};

int mx(int a, int b){
	return (a>b) ? a : b;
}

int mn(int a, int b){
	return (a<b) ? a : b;
}

vector<int> ans;

int minV = 2147483647;

void gx(int tempW, int tempL){
	int tempAns = tempW * tempL;
	if(tempAns > minV) return;
	if(tempAns < minV){
		minV = tempAns;
		ans.clear();
		ans.push_back(mn(tempW, tempL));
		return;
	}
	ans.push_back(mn(tempW, tempL));
}

int main() {
	
	int len[4][2];
	for(int i = 0; i < 4; i++){
		for(int j = 0; j < 2; j++){
			cin >> len[i][j];
		}
	}
	
	for(int i = 0; i < 24; i++){
		for(int j = 0; j < 16; j++){
			int bits[4];
			for(int k = 0; k < 4; k++){
				bits[k] = ((j & (1<<k)) > 0) ? 1 : 0;
			}
			int l[5], w[5];
			for(int k = 1; k <= 4; k++){
				l[k] = len[perm[i][k-1]-1][lw[bits[k-1]][0]];
				w[k] = len[perm[i][k-1]-1][lw[bits[k-1]][1]];
			}
			int tmpW, tmpL;
			//1
			tmpW = w[1]+w[2]+w[3]+w[4];
			tmpL = mx(l[1], mx(l[2], mx(l[3], l[4])));
			gx(tmpW, tmpL);
			//2
			tmpW = mx(l[1], mx(l[2], l[3])) + l[4];
			tmpL = mx(w[4], w[1]+w[2]+w[3]);
			gx(tmpW, tmpL);
			//3
			tmpW = mx(l[4], mx(l[1], l[2]) + l[3]);
			tmpL = w[4] + mx(w[1]+w[2], w[3]);
			gx(tmpW, tmpL);
			//4
			tmpW = mx(l[1]+l[2], mx(l[3], l[4]));
			tmpL = mx(w[1], w[2]) + w[3] + w[4];
			gx(tmpW, tmpL);
			if(w[1]+w[4] <= w[2]+w[3] && l[2] <= l[3]){
				if(w[1] <= w[2]){
					tmpW = mx(l[1]+l[2], l[3]+l[4]);
					tmpL = w[2]+w[3];
					gx(tmpW, tmpL);
				}
				else{
					tmpW = l[3] + mx(l[1], l[4]);
					tmpL = w[2] + w[3];
					gx(tmpW, tmpL);
					tmpW = mx(l[1]+l[2], l[3]+l[4]);
					tmpL = w[1]+w[3];
					gx(tmpW, tmpL);
				}
			}
		}
	}
	quickSort(ans, 0, ans.size()-1);
	cout << minV << endl;
	int l = -1;
	for(int i = 0; i < ans.size(); i++){
		if(ans[i] == l) continue;
		cout << ans[i] << " " << minV/ans[i] << endl;
		l = ans[i];
	}
	return 0;
}