T13 Delivery Club (CF875E)

· · 个人记录

T13 Delivery Club (CF875E)

这题就不是dp

CF传送门

洛谷传送门

题意简述

有两个快递员，分别在 s_1, s_2，现在有 n 个任务，每个任务 x_i 表示要将货物送到 x_i 。即让任何一个快递员到 x_i ，另一个快递员原地不动。

由于快递员之间需要有对讲机联系，请你设计一种方案使得两个快递员之间的最长距离最短。

数据范围
1 \leq n \leq 10^5 1 \leq s_1,s_2 \leq 10^9
题解

思路

看到这不禁想起了另一道题

有两个人(A和B)和n个任务，两个人完成每个任务的时间不同，但一个任务只需一个人完成。现在要求按顺序完成，两人可以同时完成不同的任务，求完成所有任务的最小时间。

两个人就比较难处理

于是不难想到多开一维，记录A的时间

设 f[i][j] 表示进行完第i个任务，A用了j的时间时，B用的时间最小值

答案即为 min(max(i,f[n][i]))

回到这道题，会发现一个比较难堪的事情：数据范围大多了！

这种做法根本行不通的 所以不要dp了

换个思路，不如先二分答案

这样问题就变为了判断两人最长距离是否能不超过 k

然后呢？正着来肯定要dfs了吧……

正着不行就反着来

送完第 i 件货物，肯定有一个人在 a_i 的

现在我们关心另一个人的位置范围，假设就是 l_i ~ r_i 吧

那 i-1 的情况肯定有一个人在 a_{i-1}

那 i-1 的情况肯定有一个人在 a_{i-1}，而另一个人的位置并没有限制（他在哪都能走到 a_i ）

所以 l_{i-1}=a_i-k，r_{i-1}=a_i+k

那还是有一个人在 a_{i-1} 里，

那另一个人又得在 a_{i-1}-k ~ a_{i-1}+k 里，又得在 l_i ~ r_i 里

l_{i-1}=max(a_{i-1}-k,l_i)$，$r_{i-1}=min(a_{i-1}+k,r_i)

那 l_{i-1}>r_{i-1} 了， return 即可（其实不 return 也行，到最后也会 return 掉）

最后会得到 l_1 ~ r_1

我们只需要一个人在这个范围里就行了

因为另一个人只要跟他距离不超过 k ，就肯定能来到 a_1

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,s1,s2;
int a[100005];
bool check(int k){
    int l=-1e9,r=1e9;
    for(int i=n;i>=1;i--){
        if(l<=a[i] && a[i]<=r) l=a[i]-k,r=a[i]+k;//a[i]在范围内 
        else l=max(l,a[i]-k),r=min(r,a[i]+k);//a[i]不在范围内 
        if(l>r) continue; 
    }
    if((l<=s1 && s1<=r) || (l<=s2  && s2<=r)) return 1;//有一个在范围内 
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&s1,&s2);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l=abs(s1-s2),r=1e9;//注意l不能赋成1（或者在上面判断s1,s2的距离） 
    while(l!=r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d",l);
}