P9559 [SDCPC2023] D

P9559 [SDCPC2023] D

去洛谷看我的博客

思路

直接做比较难，考虑二分答案，所以我们需要想出一种时间复杂度还行的方法检查答案是否合格。

假设目前二分的答案是 x x x，那么速度低于 x x x 必然需要别人背。

那么，自然而然地想到将所有人分成两部分，那么速度低于 x x 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())p()-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("%dn",ans);}	
}