思路
直接做比较难，考虑二分答案，所以我们需要想出一种时间复杂度还行的方法检查答案是否合格。
假设目前二分的答案是 \(x\)，那么速度低于 \(x\) 必然需要别人背。
那么，自然而然地想到将所有人分成两部分，那么速度低于 \(x\) 中的所有人应当优先满足较重的，如果优先满足较轻的，就可能导致较重的无法被满足。
同时，速度低于 \(x\) 的人中，最重的，应该用速度和体重之和最大的人来满足，如果满足不了，这个答案就肯定无法满足，如果能满足就可以继续看下一组人。
具体实现可以用优先队列排序，每次取最大的。
AC 代码
#include<bits/stdc++.h>
using namespace std;
struct node{int v,w;}t[100005];
inline bool cmp(node a,node b){return a.v<b.v;}
int T,n,l,r,mid,ans;
inline bool check(int x)
{
priority_queue<int>l,r;
for(int i=1;i<=n;++i)
{
if(t[i].v>=x) r.push(t[i].w+t[i].v);//分成两个部分，速度满足条件的要看速度和体重之和
else l.push(t[i].w);//速度不满足的只看体重
}
while(!l.empty()&&!r.empty())
if(r.top()-l.top()>=x) l.pop(),r.pop();//每次看最大的一组人是否满足条件
else return 0;
return (l.empty());//如果最后剩的是速度低的人也不满足条件
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&t[i].v,&t[i].w);
sort(t+1,t+n+1,cmp),l=0,r=1000000000,ans=0;
while(l<=r)//二分答案
{
mid=l+r>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
}