CF 343C

作者: ffacs 分类: 题目 发布时间: 2019-12-31 03:42

Problem Description

​ Mad scientist Mike does not use slow hard disks. His modification of a hard drive has not one, but \(n\) different heads that can read data in parallel.

When viewed from the side, Mike's hard drive is an endless array of tracks. The tracks of the array are numbered from left to right with integers, starting with \(1\). In the initial state the \(i-th\) reading head is above the track number \(h_i\). For each of the reading heads, the hard drive 's firmware can move the head exactly one track to the right or to the left, or leave it on the current track. During the operation each head's movement does not affect the movement of the other heads: the heads can change their relative order; there can be multiple reading heads above any of the tracks. A track is considered read if at least one head has visited this track. In particular, all of the tracks numbered \(h_1, h_2,..., h_n\) have been read at the beginning of the operation.

img
img

Mike needs to read the data on \(m\) distinct tracks with numbers \(p_1\), \(p_2\), ..., \(p_m\)​. Determine the minimum time the hard drive firmware needs to move the heads and read all the given tracks. Note that an arbitrary number of other tracks can also be read.

Input

​ The first line of the input contains two space-separated integers \(n,m(1 \leq n,m \leq  10^{10})\)— the number of disk heads and the number of tracks to read, accordingly. The second line contains \(n\) distinct integers \(h_i\) in ascending order\((1 \leq h_i \leq  10^{10}, h_i< h_{i + 1})\) — the initial positions of the heads. The third line contains \(m\) distinct integers \(p_i\) in ascending order \((1 \leq p_i \leq  10^{10}, p_i< p_{i + 1})\) - the numbers of tracks to read.

Output

Print a single number — the minimum time required, in seconds, to read all the needed tracks.

Solution

​ 刚开始看错题意了,以为是求最短移动距离和。

​ 最小时间应该算是一个比较明显的二分条件,时间长更接近完成。所以尝试二分时间。

​ 假设当前需要check的时间是\(x\),我们如何确定在\(x\)的时间内能否遍历全部位置呢?从左往右遍历磁头,我们发现,如果当前磁头不能把左边剩余需要访问的点都访问到,那么右边的点就更加不可能了。所以对当前磁头,我们要保证把左边剩余的访问点都访问。如果有不能那么就check失败。其次,在保证能访问完的情况下,磁头也许还有一些剩余时间,我们不能让他不干事情,得让他发挥剩余价值--让他尽可能地向右边拓展,这能减轻他右边点的压力。如果当前磁头左边本来就没有剩余要访问的点了,就直接让他向右走到最远。

​ 总结一下就是:

  • 二分时间
  • 从左往右遍历磁头
    • 如果左边有剩余需要遍历的,在确保能访问的情况下求出向右最远距离
      • 先向左再向右
      • 先向右再向左
    • 如果没有直接求出最远距离

最后就是根据思路完成代码

大致代码:

const int maxn=1e5+5;
ll hd[maxn],pos[maxn],n,m;
bool check(ll x){
    ll now=1;
    for(rg int i=1;i<=n;i++){
        if(hd[i]-pos[now]>x) return 0;
        ll s;
        if(hd[i]>pos[now]) s=max((x+pos[now]+hd[i])/2,x+2*pos[now]-hd[i]);//先右和先左
        else s=hd[i]+x;
        for(rg int j=now;j<=m&&pos[j]<=s;j++) now=j+1;//根据当前能到最右,更新最左未被访问
        if(now>m) return 1;
    }
    return 0;
}
int main() {
    n,m;cin>>n>>m;
    for(rg int i=1;i<=n;i++) read(hd[i]);
    for(rg int i=1;i<=m;i++) read(pos[i]);
    ll l=-1,r=1e18;//下界是-1,上界开大就行
    while (l+1<r){
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注