[CF 529B] Group Photo 2

作法：

如果相片的高度確定了，那麼就會有一些人必須要橫著擺，有一些人不一定需要橫著擺。因此考慮枚舉相片的高度，這樣變成要讓相片寬度最小。設當前高度為 h ，如果有一個人的長寬都 > h ，那麼這張相片就不可能拍出了。而對於高度 > h 的人就必須把他擺橫的，至於高度和寬度都 <= h 的人，假設他高 x 寬 y，先考慮把他直著擺，那麼之後把他橫著擺時就可以減少 x - y 的高度，因此如果在「必須要橫著擺的人」橫著放後，還有剩一些空間可以多幾個人橫著放，就按照「這個人橫著放後可以減少的寬度」由大到小排序，取最大的前幾個就可以了。

code :

#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
const int maxn=1000+10 ;
 
int w[maxn],h[maxn] ;
int tmp[maxn] ;
main()
{
    int n ; scanf("%d",&n) ;
    int ma=0 ;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&h[i]) ;
        ma=max(ma,max(w[i],h[i])) ;
    }
 
    int ans=INF ;
    for(int i=ma;i>=1;i--)
    {
        int cnt=0,ok=1,num=n/2,sum=0 ;
        for(int j=1;j<=n;j++)
        {
            if(h[j]>i && w[j]>i) { ok=0 ; break ; }
            if(h[j]>i) num-- , sum+=h[j] ;
            else if(w[j]>i) sum+=w[j] ;
            else sum+=w[j] , tmp[cnt++]=h[j]-w[j] ;
        }
        if(!ok || num<0) break ;
        sort(tmp,tmp+cnt) ;
        for(int i=0;i<num && i<cnt && tmp[i]<0;i++)
            sum+=tmp[i] ;
        ans=min(ans,sum*i) ;
    }
    printf("%d\n",ans) ;
}