题目链接：点击打开链接
题意：
给定n个矩形的(w, h)，把这些矩形并排放在x轴上，占用的面积为所有矩形在x轴上占用的宽度*(最高的矩形高度) 也就是用一个大框框起来。
使得占用面积最小，，输出这个占用的最小面积。
这些矩形可以选 n/2 个倒放(即(h, w) )
思路：
1、首先枚举最高的那个 a[i]
若a[j] 比 a[i]高，则j必须横放。
把所有必须横放的选择好。计算出还能再横放的个数siz
则每一次横放都可能带来代价的减小，取能减小最多的siz个代价（注意有的矩阵只能竖放，因为若横放则高度就>a[i]了）
2、可能最高的那个本身就是横放产生的，所以枚举最高的且是横放的，其他计算同1
#include<iostream>#include<stdio.h>#include<string.h>#include <algorithm>#include<string>#include<set>#include<vector>#include<queue>#include<math.h>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;typedef long long ll;const int N = 1005;struct node{int w, h;}a[N];int n;bool vis[N];int siz;vector<int>myset;int main(){while (cin >> n){for (ll i = 1; i <= n; i++){ rd(a[i].w); rd(a[i].h); }int ans = 1e9;for (int i = 1; i <= n; i++){memset(vis, 0, sizeof vis);int w = a[i].w, ok = false;siz = 0;for (ll j = 1; j <= n; j++){if (i == j)continue;if (a[i].h<a[j].h){if (a[j].w > a[i].h){ ok = true; break; }//a[i]不可能是最高的siz++, w += a[j].h;vis[j] = true;//a[j]必须横放}else w += a[j].w;}if (ok || siz * 2 > n)continue;for (ll j = 1; j <= n; j++)if (vis[j]) swap(a[j].h, a[j].w);int tmp = w*a[i].h;siz = (n – siz * 2) / 2; //siz个自由元myset.clear();for (int j = 1; j <= n; j++){if (i == j || vis[j] || a[j].w > a[i].h)continue;int x = a[j].w*a[i].h – a[j].h * a[i].h;if (x > 0)myset.push_back(x);}sort(myset.begin(), myset.end());for (ll j = (int)myset.size() – 1; j >= 0 && siz; j–, siz–)tmp -= myset[j];for (int j = 1; j <= n; j++)if (vis[j]) swap(a[j].h, a[j].w);ans = min(ans, tmp);}for (int i = 1; i <= n; i++){memset(vis, 0, sizeof vis);swap(a[i].h, a[i].w);int w = a[i].w, ok = false;siz = 1;for (ll j = 1; j <= n; j++){if (i == j)continue;if (a[i].h<a[j].h){if (a[j].w > a[i].h){ ok = true; break; }siz++, w += a[j].h;vis[j] = true;}else w += a[j].w;}if (ok || siz * 2 > n){swap(a[i].h, a[i].w);continue;}for (ll j = 1; j <= n; j++)if (vis[j]) swap(a[j].h, a[j].w);int tmp = w*a[i].h;siz = (n – siz * 2) / 2;myset.clear();for (int j = 1; j <= n; j++){if (i == j || vis[j] || a[j].w > a[i].h)continue;int x = a[j].w*a[i].h – a[j].h * a[i].h;if (x > 0)myset.push_back(x);}sort(myset.begin(), myset.end());for (ll j = (int)myset.size() – 1; j >= 0 && siz; j–, siz–)tmp -= myset[j];for (int j = 1; j <= n; j++)if (vis[j]) swap(a[j].h, a[j].w);ans = min(ans, tmp);swap(a[i].h, a[i].w);}pt(ans); puts("");}return 0;}
看不见我将要去的地方，记不得我已经去过的地方。
