【問題描述】
假設這是一個二次元。
LYK召集了n個小伙伴一起來拍照。他們分別有自己的身高Hi和寬度Wi。
為了放下這個照片并且每個小伙伴都完整的露出來，必須需要一個寬度為ΣWi，長度為max{Hi}的相框。（因為不能疊羅漢）。
LYK為了節省相框的空間，它有了絕妙的idea，讓部分人躺著！一個人躺著相當于是身高變成了Wi，寬度變成了Hi。但是很多人躺著不好看，于是LYK規定最多只有n/2個人躺著。（也就是說當n=3時最多只有1個人躺著，當n=4時最多只有2個人躺著）
LYK現在想問你，當其中部分人躺著后，相框的面積最少是多少。
【輸入格式】
第一行一個數n。
接下來n行，每行兩個數分別是Wi,Hi。
【輸出格式】
你需要輸出這個相框的面積最少是多少。
【樣例輸入】
3
3 1
2 2
4 3
【樣例輸出】
27
【樣例解釋】
如果沒人躺過來，需要27的面積。
我們只要讓第1個人躺過來，就只需要21的面積！
【數據規模與約定】
對于30%的數據n<=10。
對于60%的數據n<=1000，Wi,Hi<=10。
對于100%的數據1<=n,Wi,Hi<=1000。
?
題解：
???? ①先去掉一個限制，方法是枚舉最大高度H,貪心分類討論:
????????? ·貪心策略：在高度不超過限制的情況下，使寬度增加盡可能少。
????????? 設h,w分別為當前人的高和寬，那么：
????????? (1)h>H:
??????????????? w>H:躺著還是會超出高度，不合法直接跳出。
??????????????? w<=H:躺著
????????? (2)h<=H:
???????????????? h>=w:站著(這樣寬度增加得少)
??????????????? h<w:躺著，但是由于躺的人數有限制，所以有一部分還是要站著。
?????????????? 因此特殊處理這種需要決策的情況(在h<=H&&h<w的這種情況下)：
??????????????????? 問題：這些人站著躺著的高度都不會超出H,因此考慮怎樣選擇使得總寬度最少。
??????????????????? 解決方案：先讓每個人都站著，此時總寬度設為W,然后再讓n/2個人躺下：
???????????????????????? 每個人躺下，那么這個人對W將加上值(h-w) (意思是將寬換成高的長),
???????????????????????? 那么我們希望(h-w)盡量小，因此從小到大排序然后取前n/2個躺著就可以了。
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
using namespace std;
set<int> ::iterator sit;
int ans,sum,p[1005],i,a[1005],b[1005],cnt,CNT,j,ANS,n;
int cmp(int i,int j) {return i>j;}
bool FLAG;
int main()
{ANS=1000000000;scanf("%d",&n);for (i=1; i<=n; i++)scanf("%d%d",&a[i],&b[i]);for (i=1; i<=1000; i++){sum=0; FLAG=true; cnt=0; CNT=0;for (j=1; j<=n; j++)if (b[j]<=i && (a[j]<=b[j] || a[j]>i)) sum+=a[j]; elseif (a[j]>i && b[j]>i) {FLAG=false; break;} elseif (b[j]>i) {cnt++; sum+=b[j];} else{p[++CNT]=a[j]-b[j];sum+=a[j];}if (!FLAG) continue;if (cnt>n/2) continue;sort(p+1,p+CNT+1,cmp);for (j=1; j<=min(n/2-cnt,CNT); j++) sum-=p[j];ANS=min(ANS,sum*i);}cout<<ANS;return 0;
}//Ztraveler?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
每當我在路上停下腳步，望著天空我都會看到你。
每當我從荒蕪的夢中驚醒，留著眼淚我都能感覺到你。————汪峰《母親》
)
 客戶端)
