P9559题解

· · 题解

Analysis

首先我们注意到如果一个期望最大速度无论如何都无法满足，则比它大的速度也无法满足，符合局部答案舍弃性，也可以说单调性。考虑二分。

每次二分期望最大值，然后 check 一下该期望最大值是否满足即可。

具体如何写 check 呢？

首先，如果一个人的速度小于期望最大速度，我们肯定希望他能够被一个人背起来，并且这个人背起他之后速度仍然大于等于期望最大速度。

但是注意，一个人最多只能背起一个人。这里我们就遇到了一个问题，如果一个人跑的很快，体重又很大，可以背起一个跑的很慢而且很重的人。我们却让他背一个很轻而且跑的不算慢的人。导致后面很重而且跑的很慢的人无法背起来。实际上他可以被背起来，这就会导致答案错误。

我们显然希望一个能背很重的人去背一个很重的人。（保证他自身速度大于等于期望最大值的前提下）考虑贪心。

首先，对于每个二分出来的期望最大值，我们先预处理一下如果一个人可以背人（他的速度大于等于期望最大值），他最大可以背多重的人。形式化地，若 v_i 表示这个人的速度， w_i 表示这个人的重量， x 表示当前期望最大值。则他能在满足自身速度大于等于期望最大值的前提下，能背动的最大重量是 a_i=v_i+w_i-x 。也就是把自身速度降到 x 的时候。

然后，我们对 a_i 进行从大到小排序，对速度小于等于期望最大值的人的重量进行从大到小排序。记为 q_i 。显然如果 a_i < q_i 则直接返回 false 即可。因为我们已经从大到小排序，如果当前人能背动的最大重量小于当前人的重量则后面也一定背不动。

总结：本题考察二分答案应用。在写 check 函数的时候应用了贪心的思想。整体难度不大。考察基础算法熟练度。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100010;
const int INF = 1e9;
int T;
int n;
struct Node
{
    int v,w;
}A[N],B[N];
bool check(int x)
{
    vector <int> p,q;
    for(int i=1;i<=n;i++) if(A[i].v >= x) p.push_back(A[i].v+A[i].w-x);
    for(int i=1;i<=n;i++) if(B[i].v < x) q.push_back(B[i].w);
    if(p.size() < q.size()) return false;
    for(int i=0;i<q.size();i++)
    {
        if(p[i] < q[i]) return false;
    }
    return true;
}
bool cmp(Node a,Node b) 
{
    return a.w > b.w;
}
bool cmp1(Node a,Node b)
{
    return (a.v+a.w) > (b.v+b.w);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--)
    {   
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>A[i].v>>A[i].w;
            B[i].v = A[i].v;
            B[i].w = A[i].w;
        }
        sort(A+1,A+n+1,cmp1);
        sort(B+1,B+n+1,cmp);
        int l = 0,r = INF;
        while(l < r)
        {
            int mid = (l+r+1) / 2;
            if(check(mid)) l = mid;
            else r = mid-1;
        }
        cout<<l<<endl;
    }
}