Fast and Fat

Problem Statement

您正在参加一场团体越野比赛。您的队伍共有 $n$ 名队员，其中第 $i$ 名队员的速度为 $v_i$，体重为 $w_i$。

比赛允许每名队员独立行动，也允许一名队员背着另一名队员一起行动。当队员 $i$ 背着队员 $j$ 时，如果队员 $i$ 的体重大于等于队员 $j$，则队员 $i$ 的移动速度不会变化，仍然为 $v_i$；如果队员 $i$ 的体重小于队员 $j$，则队员 $i$ 的移动速度会减去两者的体重差值，即变为 $v_i - (w_j - w_i)$。如果队员 $i$ 的移动速度将变为负数，则队员 $i$ 无法背起队员 $j$。每名队员最多只能背负另一名队员，被背负的队员无法同时背负其他队员。

所有未被背负的队员中，最慢的队员的速度，即为整个队伍的速度。求整个队伍能达到的最大速度。

Input

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^5$）表示队员人数。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $v_i$ 和 $w_i$（$1 \le v_i, w_i \le 10^9$）表示第 $i$ 名队员的速度和体重。

保证所有数据中 $n$ 之和不超过 $10^5$。

Output

每组数据输出一个整数，表示整个队伍可以达到的最大速度。

Sample Input

Sample Output

Explanation of Example

队员 $1$ 背起队员 $4$。因为 $w_1 > w_4$，因此队员 $1$ 速度不变，仍然为 $10$。
队员 $3$ 背起队员 $2$。因为 $w_3 < w_2$，因此队员 $3$ 的速度减少 $w_2 - w_3 = 2$，即速度变为 $10 - 2 = 8$。
队员 $5$ 独立行动，速度为 $9$。

因此答案为 $8$。

Solving

题目要求在满足题目条件的情况下整个队伍最慢速度的最大值，即求整个队伍的最小值的最大值，考虑二分其速度x:

对每人进行简单的分析可以得到，每人所能背起的人的最大重量为$w_i + v_i + x$

而且对于此类的贪心同时也是一个经典模型：

有 p 个人和 q 件工作，第 i 个人的能力值为 $a_i$，第 i 项工作的难度为 $b_i$，只有 $a_i ≥ b_j$ 才能让第 i 个人做第 j 项工作。每个人最多做一项工作，问所有工作是否都能被完成。这是一个经典的贪心问题。首先选出能力值最高的 q 个人，然后将第 i 难的工作派给能力值第 i 高的人即可

所以我们只需要在二分时，将速度小于X的人列为需要被背的人，速度大于等于X的人列为需要背别人的人，然后排序判断即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


void solve()
{
    int n;
    cin >> n;
    struct node
    {
        int v,w;
    }a[n+1];
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].v >> a[i].w;
    }
    int l = 0,r = 1e9,mid;
    auto check = [&](int x)
    {
        vector<int> pick;//需要背人
        vector<int> non;//需要被人背
        for(int i=1;i<=n;i++) if(a[i].v >= x) pick.push_back(a[i].v + a[i].w - x);//此人能背的最大重量
        else non.push_back(a[i].w);
        if(non.size()>pick.size()) return false;
        sort(pick.begin(),pick.end(),greater<int>());//按能背的最大重量从大到小排序
        sort(non.begin(),non.end(),greater<int>());//把需要被人背的人按体重从大到小排序
        for(int i=0;i<non.size();i++)
        {
            if(pick[i]<non[i]) return false;
        }
        return true;
    };
    while(l+1<r)
    {
        mid = l + r >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    if(!check(r))
    {
        r = l;
    }
    cout << r << endl;
}