泡泡堂（超详解）

题目描述

第XXXX届NOI期间，为了加强各省选手之间的交流，组委会决定组织一场省际电子竞技大赛，每一个省的代表队由n名选手组成，比赛的项目是老少咸宜的网络游戏泡泡堂。每一场比赛前，对阵双方的教练向组委会提交一份参赛选手的名单，决定了选手上场的顺序，一经确定，不得修改。比赛中，双方的一号选手，二号选手……，n号选手捉对厮杀，共进行n场比赛。每胜一场比赛得2分，平一场得1分，输一场不得分。最终将双方的单场得分相加得出总分，总分高的队伍晋级(总分相同抽签决定)。
作为浙江队的领队，你已经在事先将各省所有选手的泡泡堂水平了解的一清二楚，并将其用一个实力值来衡量。为简化问题，我们假定选手在游戏中完全不受任何外界因素干扰，即实力强的选手一定可以战胜实力弱的选手，而两个实力相同的选手一定会战平。由于完全不知道对手会使用何种策略来确定出场顺序，所以所有的队伍都采取了这样一种策略，就是完全随机决定出场顺序。
当然你不想这样不明不白的进行比赛。你想事先了解一下在最好与最坏的情况下，浙江队最终分别能得到多少分。
 

输入

第一行为一个整数n，表示每支代表队的人数。
接下来n行，每行一个整数，描述了n位浙江队的选手的实力值。
接下来n行，每行一个整数，描述了你的对手的n位选手的实力值。
20％的数据中，1<=n<=10；
40％的数据中，1<=n<=100；
60％的数据中，1<=n<=1000；
100％的数据中，1<=n<=100000，且所有选手的实力值在0到10000000之间。
 

输出

包括两个用空格隔开的整数，分别表示浙江队在最好与最坏的情况下分别能得多少分。不要在行末输出多余的空白字符。

样例输入

2
1
3
2
4

样例输出

2 0

提示

我们分别称4位选手为A,B,C,D。则可能出现以下4种对战方式，最好情况下可得2分，最坏情况下得0分。

思路：读完题很快就联想到了田忌赛马，用最弱的去对抗最强的，以获得最大收益。但是，田忌赛马的情况是，每一种类型的马都要比对方差，如果一对一去碰，肯定会都输掉，而用弱的去碰最强，次强去碰弱，强碰次强的策略可以最大化最终的得分。而在这道题中，我们并不知道双方的总体实力，如果我方是碾压式的强者，那么我并不需要让我们弱的去碰对面强的，只需要按实力从低到高逐个去对战，就会全部取得胜利。

可见，这题的关键在于到底要不要牺牲弱的耗掉对方最强的。

（1）如果我们的弱的要比对方强，那我们肯定会选择2分的胜利而不是牺牲；

（2）如果我们的弱的要比对方的弱，那么无论怎样我方弱的是一定会输的，不如让他输的有价值一点，去消耗掉对方最强的；

（3）但还有个问题是弱的和弱的相等的情况，这时，我们究竟是该拿到平局的1分，还是去消耗掉强者，以实现田忌赛马，将本来的一场负换成一个2分的胜局呢？我们就还需要去看强者，如果我方的强者更强，那肯定就不需要弱的去牺牲，选择1分的平局就好了，但是我方的强者弱于或平于对方，那么我们就需要牺牲弱的了，让弱的去跟对面最强的比，而我们的强者是一定会大于或平于对面的最弱的（因为我方和对面最弱相等），所以肯定会比之前平局的情况好。

还有一个小细节就是，牺牲弱的，让弱的去跟对面强的打，不一定我方弱的都会输，我们前面已经分析过了，牺牲弱的要么是我方弱的小于对面的，要么是平于对面弱的，小于的话，肯定都会输，但是如果是平于的话，如果对方实力很平均，全部相等，那么我方弱的还会平于对方强的，所以还要加一个特判，如果平局的话，+1

（4）至于最坏的情况，就很简单了，我们直接算对面最好的情况，然后发现每一局无论最后结果如何两方得分的和都为2，最后用2*n减去对方得分就好了

AC代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100010;
int a[N],b[N];
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int a1=1,an=n,b1=1,bn=n,ans=0;
for (int i=1;i<=n;i++){
if (a[a1]>b[b1]){
ans+=2;
a1++,b1++;
}
else if (a[a1]<b[b1]){//牺牲
a1++,bn–;
}
else{
if (a[an]>b[bn]){
ans+=2;
an–,bn–;
}
else{//牺牲
if (a[a1]==b[bn])
ans+=1;
a1++,bn–;
}
}
}
cout<<ans<<' ';
a1=1,an=n,b1=1,bn=n,ans=0;
for (int i=1;i<=n;i++){
if (b[b1]>a[a1]){
ans+=2;
b1++,a1++;
}
else if (b[b1]<a[a1]){
b1++,an–;
}
else{
if (b[bn]>a[an]){
ans+=2;
bn–,an–;
}
else{
if (b[b1]==a[an])
ans+=1;
b1++,an–;
}
}

}
cout<<2*n-ans;
}

（最后补充一点，上面的代码是根据每一轮进行模拟的，所以在else分支中我们比较强者时，如果     我方强者大，虽然我们的策略是保留弱者平局的情况，但是由于我们一轮只处理一对，所以只需     要让两个强者匹配）