Codeforces 529B Group Photo 二 规律题

Codeforces 529B Group Photo 2 规律题

题目链接：点击打开链接

题意：

给定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;
}