洛谷P2587 [ZJOI2008] 泡泡堂

时间:2021-07-31 15:27:43

  题目传送门


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

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

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

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

  这个正确性应该不难证明,那么最大的得分就这么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 ;
}