Codeforces Global Round 17 C. Keshi Is Throwing a Party

C. Keshi Is Throwing a Party
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Keshi is throwing a party and he wants everybody in the party to be happy.

He has n
friends. His i-th friend has i

dollars.

If you invite the i
-th friend to the party, he will be happy only if at most ai people in the party are strictly richer than him and at most bi

people are strictly poorer than him.

Keshi wants to invite as many people as possible. Find the maximum number of people he can invite to the party so that every invited person would be happy.
Input

The first line contains a single integer t
(1≤t≤104)

— the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n
(1≤n≤2⋅105)

— the number of Keshi’s friends.

The i
-th of the following n lines contains two integers ai and bi (0≤ai,bi<n)

.

It is guaranteed that the sum of n
over all test cases doesn’t exceed 2⋅105

.
Output

For each test case print the maximum number of people Keshi can invite.
Example
Input
Copy

3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1

Output
Copy

2
1
2

Note

In the first test case, he invites the first and the second person. If he invites all of them, the third person won’t be happy because there will be more than 1

person poorer than him.

题意：就是给定n个人，第i个人有idollar，并且有a[i]表示参会的人中比他富的不超过a[i]人,b[i]表示参会的人中比他穷的不超过b[i]，这时候没办法直接求出答案，只能二分答案，挨个贪心验证（二分答案这种算法就是为了验证我们的猜想，怎么验证呢，往往是贪心的验证，因为验证某值正确与否，要选最优解）
做法呼之欲出：二分之后怎么贪心呢，i从1到n遍历，b[i]与已经选了的人比较，a[i]与之后至少要放多少个人（ans-已选择人数-1，别忘了减自身）比较，如果都>,满足题目条件，人数++。
另外，二分的模板要记住，边界问题考虑到。

using namespace std; 
const int N=1e6+7 ; 
int a[N], b[N],rr;
bool er(int x)
{
	int ren=0;
	for(int i=1 ;i<=rr;i++)
	{
		if((b[i]>=ren)&&(a[i]>=(x-ren-1)))
		{
		ren++;
		}if(ren==x)return 1; 
	}return 0 ;
}
int main()
{
	int t; 
	cin>>t;
	while(t--)
	{
		cin>>rr; 
		for(int i= 1; i<=rr;i++)
		{
			scanf("%d%d",&a[i],&b[i]); 
		}	
		int l =1,r=rr,mid,ans;
		while(l<=r)
		{   
		     mid=(l+r)>>1;
			 if(er(mid))
			 {ans=mid;
			 l=mid+1;
			 }else r=mid-1;
		}
		cout<<ans<<endl; 
	}
	return 0 ; 
}