BZOJ 1034, 泡泡堂

Problem

传送门

Mean

参见题目描述。

Analysis

排序后套用田忌赛马的贪心思想。 1. 当己方实力值最小的选手实力值大于对方最小时，直接比赛即可； 2. 当己方实力值最大的选手实力值大于对方最大时，直接比赛即可； 3. 用己方实力值最小的选手迎战对方实力值最大的选手（注意判断战平的情况）。

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=100005; int n,a[N],b[N]; void read(int &x){ char c; while((c=getchar())<'0' || c>'9'); x=c-'0'; while((c=getchar())>='0' && c<='9') x=x*10+c-'0'; } int solve(int a[],int b[]){ int l1=0,l2=0,r1=n-1,r2=n-1,ans=0; while(l1<=r1){ if(a[l1]>b[l2]) ans+=2,l1++,l2++; else if(a[r1]>b[r2]) ans+=2,r1--,r2--; else ans+=a[l1++]==b[r2--]; } return ans; } int main(){ read(n); for(int i=0;i<n;i++) read(a[i]);sort(a,a+n); for(int i=0;i<n;i++) read(b[i]);sort(b,b+n); printf("%d %d",solve(a,b),(n<<1)-solve(b,a)); return 0; }