Codeforces Global Round 17 C 二分枚举答案 二分可行不可行

Codeforces Global Round 17 C 二分枚举答案 二分可行不可行 题目

有N个人可以去你家聚会，每个人有的钱是 1 2 3 … N
另外
每个人还有一些要求
比他有钱的人至多为ai个 比他穷的人至多为bi个
如果没满足要求，他就会不开心。
你想邀请最多的人，让他们都开心。
求最大的人数。

题解思路

一开始没看到at most，至多，以为是恰好那么多人。
假设存在一个答案为X人
我们从这个最优答案中从后面抽走一个人，也是可行。
因为要求是至多，而小一个人并不影响至多的情况。
所以，我们可以推出 0 到 X 直接的都是可行解。当答案大于X就是不可行的。
这样我们二分答案的可行性就能搜出答案了。
check中 实际人数 cnt <= p 的时候， 拉小范围，否则拉大。
这样我们搜出的r 就是最小的满足 cnt <= r
r的值已经接近正解了，可能会存在偏大1的情况（大于的时候 等于的时候就刚好就是正解）
我们特判就行了。

AC代码

#include 
//#include 
//priority_queue
#define PII pair
#define ll long long

using namespace std;

const  int  INF =  0x3f3f3f3f;
const  int N = 200100 ;
int a[N] ; 
int b[N] ;
int n ;

bool che(int p )
{
    int cnt = 0 ;
    for (int i = 1 ; i <= n ; i++ )
    {
        if ( p - cnt - 1 <= a[i] && cnt <= b[i] )
            cnt ++;
    }
    return cnt <= p ; 
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T ;
    cin >> T ;
    while (T--)
    {
        cin >> n ;
        for (int i = 1 ; i <= n ; i++ )
            cin >> a[i] >> b[i] ; 
        int l = 1 , r = n ;
        while ( l < r )
        {
            int mid = l + r >> 1 ;
            if (che(mid))
            {
                r = mid ;
            }else
                l = mid + 1 ; 
        }
        int cnt = 0 ;
        for (int i = 1 ; i <= n ; i++ )
        {
            if ( r - cnt - 1 <= a[i] && cnt <= b[i] )
                cnt ++;
        }
        if (cnt == r )
            cout << cnt << "n" ; 
        else
            cout << r-1 << "n" ;
    }
    return 0 ;
}