• 基本思路：贪心，每次将 $A$ 中的数从大到小与 $B$ 中的数从小到大一一对应组合，即 $A$ 中最大的数与 $B$ 中最小的数组合， $A$ 中第二小的数与 $B$ 中第二大的数组和，其中最大的数对即为所求。

• 像这样:
  

• 非常简单易懂的贪心。

• 但是俗话说得好，贪心不难，但是难的是证明。

• 非常随意的证明：

• 设数对 $(A_1,B_1)$ 是最大数对，下一个数对为 $(A_2,B_2)$ 。

• 根据我们之前的贪心思路，可知

  $A_1B_2$

• 而要使最大数对的最大值减小，要么将 $A_1$ 与 $B$ 中更小的数组合，要么将 $B_1$ 与 $A$ 中更小的数组合,以前一种方法为例，新的两个数对为

  $(A_2,B_1)$ 和 $(A_1,B_2)$

• 很容易发现

  $A_2+B_1>A_1+B_1$

• 所以这样做反而会使最大值变得更大，后一种方法也一样，因此 $(A_1,B_1)$ 一定是所求的最大数对。

• 证毕。

• 在程序的具体实现中，由于 $1\leq A_i,B_i\leq 100$ ，还可以用桶排进行优化。

• 具体看代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[105],b[105],c[105],d[105],x,y;
inline int read(){//快读 
	char ch=getchar();
	int x=0,w=1;
	while((ch>'9' || ch<'0') && ch!='-')ch=getchar();
	if(ch=='-')w=-1,ch=getchar();
	while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w; 
}
int find(){
	int i=1,j=100,maxx=0;
	for(int k=1;k<=100;k++)//因为要对数组进行操作，所以用c,d数组进行代替。 
		c[k]=a[k],d[k]=b[k];
	while(i<=100 and j>=1){
		while(!c[i] and i<=100)
			i++;
		while(!d[j] and j>=1)
			j--;
		if(i>100 or j<1)
			break;
		maxx=max(i+j,maxx);//对最大值进行更新。
		int w=min(c[i],d[j]);
		d[j]-=w;c[i]-=w;
	}
	return maxx;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		x=read();y=read();
		a[x]++;b[y]++;
		printf("%d\n",find());
	}
} 

• 然后就可以愉快地把这题水掉了。