【[ZJOI2008]泡泡堂】

想贪心就是反复\(hack\)自己的过程

首先这很田忌赛马，但是又不完全一样

田忌赛马保证了所有马的实力不同，因此没有平局

田忌赛马的策略是当自己最强的马比不过对方最强的马的时候，就用自己最弱的马来自爆，在没有平局的情况下确实是最优的，因为我们总是要保证自己最强的马获得了胜利

但是这里有了平局

情况就变得不一样起来

还是从最弱的马开始考虑

如果这匹最弱的马能战胜对方当前最弱的马，那么就去战胜对方啊，绝对不亏

如果是平局或者是失败，那么我们就去考虑一下最强的两匹马，如果此时我方最强的马可以战胜对方最强的马，那么我们还用不到这匹最弱的马来自爆，所以先让我方最强战胜对方最强

如果最强的马不能赢，那么我们就只能用最弱的马来当炮灰了，我方最弱对对方最强，无非就是一场输或者平局，而这匹最弱的马本身也不能战胜其他马了(就算那匹可以战平对方最弱的马，为什么不让我方更强一些的马来获得一场胜利呢)，所以就自爆为以后的马创造更好的机会好了

一个动态删除最大最小值的数据结构，懒得用数组和双指针了，于是用了\(multiset\)

代码

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<set>

#define re register

#define maxn 100005

int a[maxn],b[maxn];

int n;

std::multiset<int> s1,s2;

int ans;

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9')

		x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int main()

{

	n=read();

	for(re int i=1;i<=n;i++) a[i]=read(),s1.insert(a[i]);

	for(re int i=1;i<=n;i++) b[i]=read(),s2.insert(b[i]);

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

	{

		std::multiset<int>::iterator j=s1.begin(),k=s2.begin();

		if(*j>*k)

		{

			ans+=2;

			s1.erase(j),s2.erase(k);

		}

		else

		{

			j=s1.end(),k=s2.end();

			j--,k--;

			if(*j>*k) ans+=2,s1.erase(j),s2.erase(k);

			else

			{

				j=s1.begin();

				if(*j==*k) ans++;

				s1.erase(j),s2.erase(k);

			}

		}

	}

	std::cout<<ans<<" ";ans=0;

	for(re int i=1;i<=n;i++) s2.insert(a[i]);

	for(re int i=1;i<=n;i++) s1.insert(b[i]);

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

	{

		std::multiset<int>::iterator j=s1.begin(),k=s2.begin();

		if(*j>*k)

		{

			ans+=2;

			s1.erase(j),s2.erase(k);

		}

		else

		{

			j=s1.end(),k=s2.end();

			j--,k--;

			if(*j>*k) ans+=2,s1.erase(j),s2.erase(k);

			else

			{

				j=s1.begin();

				if(*j==*k) ans++;

				s1.erase(j),s2.erase(k);

			}

		}

	}

	std::cout<<(2*n-ans);

	return 0;

}