洛谷P2587 [ZJOI2008] 泡泡堂

　　题目传送门

---

　　分析：一道策略游戏题，要求最大期望得分和最小期望得分。首先分析最大，很显然是可以用一种类似于田忌赛马的思维来做，将两队的实力按照从大到小（其实从小到大也可以）排序，然后就按照顺序比较，可能会出现以下几种情况：

　　我方最大>对方最大，则用我方最大对抗对方最大

　　我方最小>对方最小，则用我方最小对抗对方最小

　　如果以上两种情况都不满足，则用我方最小去对抗对方最大，为我方最大争取机会。

　　这个正确性应该不难证明，那么最大的得分就这么A（shui）掉了；

　　再看最小得分，发现直接求最小得分并不容易，那么转换一下思维，求最大失分，再用2n-最大失分，正确性易证。那么求最大失分思维就和上面一样，只需转换一下：

　　我方最大<对方最大，则用我方最大对抗对方最大

　　我方最小<对方最小，则用我方最小对抗对方最小

　　如果以上两种情况都不满足，则比较我方最大与对方最小，如果相等，则失一分，否则不失分。

　　然后，这题就这样水过去了！

　　Code：

//It is made by HolseLee on 7th Apr 2018

//Luogu.org P2587

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<iostream>

#include<iomanip>

#include<algorithm>

using namespace std;

const int N=1e5+;

int n,a[N],b[N];

int ans,hm,tm,he,te;

inline int read()

{

  char ch=getchar();int num=;bool flag=false;

  while(ch<''||ch>''){if(ch=='-')flag=true;ch=getchar();}

  while(ch>=''&&ch<=''){num=num*+ch-'';ch=getchar();}

  return flag?-num:num;

}

bool cmp(int x,int y)

{return x>y;}

int main()

{

  n=read();

  for(int i=;i<=n;i++)

    a[i]=read();

  for(int i=;i<=n;i++)

    b[i]=read();

  sort(a+,a+n+,cmp);

  sort(b+,b+n+,cmp);

  tm=te=n;hm=he=;

  while(hm<=tm){

    if(a[hm]>b[he])ans+=,hm++,he++;

    else if(a[tm]>b[te])ans+=,tm--,te--;

    else ans+=(a[tm]==b[he]),he++,tm--;}

  printf("%d ",ans);

  hm=he=;tm=te=n;ans=;

  while(hm<=tm){

    if(a[hm]<b[he])ans+=,hm++,he++;

    else if(a[tm]<b[te])ans+=,tm--,te--;

    else ans+=(a[hm]==b[te]),hm++,te--;}

  printf("%d",*n-ans);

  return ;

}