P2587 [ZJOI2008]泡泡堂

$Result$

$Hyperlink$

https://www.luogu.com.cn/problem/P2587

$Description$

两个队伍，每个队伍各有$n$个人，$A$队第$i$个人的强度值是$a_i$，$B$队第$i$个人的强度值是$b_i$

每场比赛会从两队中各选出一个人，比较他们的强度值
强的那一方加两分，弱的那一方不加分不扣分，若强度相同，双方各加一分

求$A$队最好情况和最坏情况的得分

数据范围：$n\le 10^5$

$Solution$

田忌赛马改一改就好了。。。

首先比赛的先后顺序与答案无光，我们只关心每个人具体和谁比了
我们这边只用求最好情况就好了，因为两队总分是固定的$2\times n$，如果$B$队拿了最高分，$A$队自然就拿了最低分，最坏情况只需要把$B$队当成$A$队做就好了

考虑如何处理最好情况
直接田忌赛马的策略？

我们先概括一下田忌赛马的策略是怎样的： 让最弱的去送人头，使得强的尽量拿分

但是！我们有些时候并不需要让弱的去送人头
比如：

1. 弱的本来就吊打得过对面最弱的
2. 强的本来就吊打得过对面最强的

注意是吊打，因为如果平局我们还是让弱的去送人头比较好（这样肯定不会更劣）
考虑完这些就好了，注意特判送人头不一定送得到（可能对方最强的还没你这边最弱的强2333）

时间复杂度：$O(n\log n)$

$Code$

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 100010
using namespace std;int n,a[N],b[N];
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline int work(int a[],int b[])
{int ans=0;for(int l=1,r=n,x=1,y=n;l<=r&&x<=y;) if(a[l]>b[x]) ans+=2,l++,x++;else if(a[r]>b[y]) ans+=2,r--,y--;else ans+=a[l]==b[y],l++,y--;return ans;
}
signed main()
{n=read();for(register int i=1;i<=n;i++) a[i]=read();for(register int i=1;i<=n;i++) b[i]=read();sort(a+1,a+1+n);sort(b+1,b+1+n);printf("%d %d",work(a,b),2*n-work(b,a));
}