P2587 [ZJOI2008]泡泡堂

[ZJOI2008]泡泡堂 - 洛谷

这道题目的灵魂在于：如何将每一个选手对答案的贡献最大化或者尽量少地影响其他选手对答案的贡献最大化？

根据答案的可能性分情况讨论：

（1）这位选手对答案的贡献为2，那么对方实力值最小的选手的实力值一定比他的实力值小；

（2）如果对方没有实力值比他小的，我们可以看一看有没有实力值与他相同的，那么，对答案的为1。要注意的一点是，有可能实力值比他大的选手可以对答案作出2的贡献，因此，当这位选手的实力值只要等于对方实力值最大的选手，那么，他的贡献为1。在此之前，还要考虑实力值最大的选手是否可以完胜对方实力值最大的选手那样可以获得2的贡献。

（3）其余情况这位选手对答案的贡献都为0。

因为上述操作的实际需要，我们需要将每个选手按实力值从小到大排序。

#代码

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 100010
int n,a[N],b[N];

int read ()
{
	int s=0,k=1;char c=getchar ();
	while (!isdigit (c)) {if (c=='-') k=-1;c=getchar ();}
	while (isdigit (c)) {s=s*10+c-'0';c=getchar ();}
	return k*s;
}

void Init ()
{
	n=read ();
	for (int i=1;i<=n;i++)
		a[i]=read ();
	for (int i=1;i<=n;i++)
		b[i]=read ();
}

int Handle (int a[],int b[])
{
	int h1,h2,r1,r2,res=0;
	h1=h2=1;r1=r2=n;
	while (h1<=r1 && h2<=r2)
	{
		if (a[h1]>b[h2])
		{
			res+=2;
			h1++;
			h2++;
		}
		else if (a[r1]>b[r2])
			 {
			 	  res+=2;
			 	  r1--;
			 	  r2--;
			 }
			 else
			 {
			 	  if (a[h1]==b[r2])
			 		  res++;
			   	  h1++;
			 	  r2--;
			 }
	}
	return res;
}

void Work ()
{
	sort (a+1,a+1+n);
	sort (b+1,b+1+n);
	cout<