贪心
枚举最后方案中最大的h，设为maxh
若某个人i的wi与hi均大于maxh，则此方案不可行
若某个人恰有一个属性大于maxh，则可确定他是否换属性
剩下的人按wi-hi从大到小排序后贪心选择
O(nlogn+n2)
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=;
int n,w[maxn],h[maxn],hh,ans=1e9,sw;
bool cmp(const int &a,const int &b)
{
return w[a]-h[a]>w[b]-h[b]; //按wi-hi排序
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&w[i],&h[i]);
hh=max(w[i],max(hh,h[i])),sw+=w[i];
}
for(int maxh=;maxh<=hh;maxh++)
{
int cnt=,rs=sw;
vector<int>v;
for(int i=;i<=n;i++) //分类讨论
{
if(w[i]>maxh&&h[i]>maxh)
{
cnt=1e9;
break;
}
else if(w[i]>maxh&&h[i]<=maxh)
continue;
else if(w[i]<=maxh&&h[i]>maxh)
{
rs+=h[i]-w[i];
cnt++;
}
else if(w[i]>h[i])
v.push_back(i); //把待处理元素放入vector
}
if(cnt>n/)
continue;
sort(v.begin(),v.end(),cmp);
for(int i=;i<v.size()&&cnt+i<n/;i++)
rs+=h[v[i]]-w[v[i]];
ans=min(ans,rs*maxh);
}
printf("%d\n",ans);
return ;
}