傳送門

解題思路

這道題要用到貪心的思路，首先要枚舉一個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; }

轉載于:https://www.cnblogs.com/sdfzsyq/p/9676952.html

總結

以上是生活随笔為你收集整理的CF 529B Group Photo 2 (online mirror version)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。