CF 529B Group Photo 2 (online mirror version)

传送门

解题思路

这道题要用到贪心的思路，首先要枚举一个h的最大值，之后check。如果这个东西的w[i]与h[i]都大于枚举的值就直接return false，如果w[i]比这个值小，h[i]比这个值大，就将h[i]与w[i]交换，注意并不能直接交换因为后面还要用到，要在答案中将h[i]加上。如果交换次数比n/2大也return false，如果w[i]与h[i]均比这个值小，则将w[i]-h[i]加入数组。后面将它排序，选出可以被交换的更新答案。

代码

#include<iostream>
#include<cstdio> 
#include<algorithm>
#define int long longusing namespace std;
const int MAXN = 1005;inline int rd(){int x=0,f=1;char ch=getchar();while(!isdigit(ch))  {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch))   {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; 
} int n,w[MAXN],h[MAXN];
int ans=1e18+1,sum;
int cnt,upd[MAXN];inline bool cmp(int x,int y){return x>y;
}inline bool check(int x){int k=0;cnt=0;for(register int i=1;i<=n;i++){if(w[i]>x && h[i]>x) return false;if(h[i]>x && w[i]<=x) k++,sum+=h[i],sum-=w[i]; else if(h[i]<=x && w[i]<=x)  upd[++cnt]=w[i]-h[i];sum+=w[i];}if(k>n/2) return false;sort(upd+1,upd+1+cnt,cmp);int res=n/2-k;for(register int i=1;i<=res && i<=cnt;i++){if(upd[i]<=0) break;sum-=upd[i];}sum*=x; return true;
}
signed main(){n=rd();int mx=0;for(register int i=1;i<=n;i++)w[i]=rd(),h[i]=rd(),mx=max(w[i],max(mx,h[i]));for(register int i=1;i<=mx;i++){sum=0;if(!check(i)) continue;ans=min(ans,sum);}printf("%lld",ans); return 0;
}