校园趣味接力 难度：中阶 时间限制：2000ms 内存限制：256MB

Question

C++题目描述
你和你的同学们要参加一场校园趣味接力赛跑。你的队伍共有n名同学，其中第i名同学的奔跑速度为vi，体重为wi。

比赛允许每名同学独立奔跑，也允许一名同学背着另一名同学一起奔跑。当同学i背着同学j时：

如果同学i的体重大于等于同学j的体重，则同学i的奔跑速度不会变化，仍然为vi。
如果同学i的体重小于同学j的体重，则同学i的奔跑速度会减去两者的体重差值，即变为vi-(wj-wi)。如果同学i的奔跑速度变为负数，则同学i无法背起同学j。
每名同学最多只能背负一名其他同学，被背负的同学无法同时背负其他同学。

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

输入格式
第一行输入一个整数t表示测试数据组数，对于每组测试数据：

第一行输入一个整数n表示同学人数。

接下来n行，每行输入两个整数vi和wi表示第i名同学的奔跑速度和体重。

保证所有数据中n之和不超过10的5次方。

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

样例
样例输入

2
5
10 5
1 102
10 100
7 4
9 50
2
1 100
10 1

样例输出

8
1

提示
在第一个样例数据中，最优策略如下：

同学 1 背起同学 4，因为同学 1 的体重大于同学 4，因此同学 1 速度不变，仍然为 10。
同学 3 背起同学 2，因为同学 3 的体重小于同学 2，因此同学 3 的速度减少w2-w3=2，即速度变为10-2=8。
同学 5 独立奔跑，速度为 9。
因此，整个队伍的速度为 8。

数据范围
对于50%的数据，1<=n<=10的4次方,1<=v,w<=10的3次方,1<=t<=10

对于100%的数据，1<=n<=10的5次方,10的3次方1<=v,w<=10的9次方,1<=t<=10

Answer 1

#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
using namespace std;
typedef pair<long long, long long> pll;

int n;

pll A[MAXN + 10], B[MAXN + 10];

// 检验答案 x，转换成贪心
bool check(long long x) {
    vector<long long> P, Q;
    // 计算哪些队员可以背别人，即为贪心问题中每个人的能力值
    for (int i = 1; i <= n; i++)
        if (A[i].first >= x) P.push_back(A[i].first + A[i].second - x);
    // 计算哪些队员需要别人背，即为贪心问题中工作的难度
    for (int i = 1; i <= n; i++)
        if (B[i].first < x) Q.push_back(B[i].second);
    // 因为 A 和 B 已经从大到小排过序了，所以 P 和 Q 也已经是有序的，不需要 sort
    // 把第 i 难的工作分给能力值第 i 大的人
    if (P.size() < Q.size()) return false;
    for (int i = 0; i < Q.size(); i++) if (P[i] < Q[i]) return false;
    return true;
}

void solve() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        long long v, w; scanf("%lld%lld", &v, &w);
        A[i] = B[i] = pll(v, w);
    }
    // 将队员按 v_i + w_i 从大到小排序，记在 A 里
    sort(A + 1, A + n + 1, [](pll &a, pll &b) {
        return a.first + a.second > b.first + b.second;
    });
    // 将队员按 w_i 从大到小排序，记在 B 里
    sort(B + 1, B + n + 1, [](pll &a, pll &b) {
        return a.second > b.second;
    });

    // 二分答案
    long long head = A[1].first, tail = A[1].first;
    for (int i = 2; i <= n; i++) {
        head = min(head, A[i].first);
        tail = max(tail, A[i].first);
    }
    while (head < tail) {
        long long mid = (head + tail + 1) >> 1;
        if (check(mid)) head = mid;
        else tail = mid - 1;
    }
    printf("%lld\n", head);
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}