Description

Alice和Bob在玩一个游戏，每一轮Bob都会给Alice两个整数A和B(1<=A,B<=100)，Alice每一轮必须把目前所有的A序列和B序列中的数一一配对，每个数必须用且只使用一次，要求最大和最小。

Input

第一行一个整数N(1<=N<=100000)，表示比赛的轮数。
　　接下来N行每行包含两个整数A和B(1<=A,B<=100)，表示Bob这一轮给的两个数。

Output

输出N行，每行输出最小的最大和。

Sample Input

输入1：

3
2 8
3 1
1 4

输入2：

3
1 1
2 2
3 3

Sample Output

输出1：

10
10
9

输出2：

2
3
4

Hint

【样例解释】

样例1中，第一轮的A序列为{2},B序列为{8}，只能是(2,8)，答案为10；
　　第二轮A序列为{2,3}，B序列{8,1}，可以采用配对(2,8),(1,3)，这样的配对最大的和是10，是最小的配对方案；
　　第三轮A序列为{2,3,1}，B序列为{8,1,4}可以采用配对(2,1),(3,4),(1,8)，最大的和为9，没有比这更小的配对方案。

【数据范围】

50%的数据N<=200

题解

题目大意

每次给出A，B两数，两两匹配，问每次的最小最大和。

思路

一开始是想怎样才能满足最小最大和，不过很快就想到了…(废话 )
挺明显的，A按升序，B按降序，两两匹配，就是最小最大和。
然后…两个堆…欧！！！
接下来N行每行包含两个整数A和B(1<=A,B<=100)
(1<=A,B<=100)
(1<=A,B<=100)
(1<=A,B<=100)
哈哈
桶，一下就过了

代码

#include<bits/stdc++.h>
#define rg register
#define Fu(i,a,b) for(rg int i=(a);i<=(b);i++)
#define Fd(i,a,b) for(rg int i=(a);i>=(b);i--)
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;
int n,a[105],b[105],ans;
void change(int j,int js){
	if(b[js]!=0) ans=max(ans,j+js);
} 
int main(){
	scanf("%d",&n);
	Fu(i,1,n){
		int ai,bi,numa=0,numb=0,js=100;
		ans=0;
		scanf("%d%d",&ai,&bi);
		a[ai]++,b[bi]++;
		Fu(j,1,100){
			if(a[j]!=0){
				numa=a[j];
				if(numb!=0){
					if(numb<=numa){
						change(j,js+1);
						numa-=numb;
					}
					else{
						change(j,js+1);
						numb-=numa;
						continue;
					}
				}
				while(numa-b[js]>0){
					change(j,js);
					numa-=b[js],js--;
				}
				change(j,js);
				numb=b[js]-numa,js--;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}