题解归档 - cf343C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf343C
• 本地来源：problems/cf343C/idea.md
• 题目链接：https://codeforces.com/contest/343/problem/C
• 原始标题：cf343C — Read Time

思路

cf343C — Read Time

题意

(n) 个磁头初始在升序位置 (h_i)，每秒各磁头可左/右移动 1 格或不动；磁头可交叉、同轨可多头。轨道 (p_1<\cdots<p_m) 需被至少一头经过（初始 (h_i) 已算读过）。求读完所有 (p_j) 的最少秒数。

做法

二分答案 (T)，检验是否能在 (T) 秒内读完。

检验前先跳过已在初始磁头位置上的 (p_j)（(T=0) 时可能已全部满足）。

从左到右枚举磁头，维护第一个未读目标下标 (j)：

1. 若 (p_j > h_i+T)：该头够不着当前目标，跳过此头。
2. 若 (p_j < h_i-T)：该头无法在 (T) 秒内到达 (p_j)，失败。
3. 否则该头先走到 (p_j)，耗时 (|h_i-p_j|)，剩余 (T-|h_i-p_j|) 秒继续向右扫，最远到 (p_j + (T-|h_i-p_j|))，把该区间内所有 (p) 标记已读。

全部磁头处理完 (j=m) 则可行。答案上界取 (10^{18}) 量级。

复杂度

二分 (\log 10^{18})，每次检验 (O(n+m))，总 (O((n+m)\log V))。

验证

样例 3 组 + 本地对拍 500 组（gen 限制 (n\le3,m\le5)，DFS 分块暴力对拍）。

代码

来源：problems/cf343C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:54:11
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
ll h[100005],p[100005],n,m,i,j,lo,hi,mid,ans,rem,mx;
bool pd(ll t){
    j=0;
    while(j<m and p[j]<=h[n-1]){
        ll zc=lower_bound(h,h+n,p[j])-h;
        if(zc<n and h[zc]==p[j]) j++;
        else break;
    }
    if(j>=m) return 1;
    for(i=0;i<n;i++){
        if(j>=m) return 1;
        if(p[j]>h[i]+t) continue;
        if(p[j]<h[i]-t) return 0;
        rem=t-abs(h[i]-p[j]);
        mx=p[j]+rem;
        while(j<m and p[j]<=mx) j++;
    }
    return j>=m;
}
int main(){
    cin>>n>>m;
    for(i=0;i<n;i++) cin>>h[i];
    for(i=0;i<m;i++) cin>>p[i];
    lo=0,hi=inf;
    while(lo<hi){
        mid=(lo+hi)/2;
        if(pd(mid)) hi=mid;
        else lo=mid+1;
    }
    cout<<lo<<endl;
    return 0;
}