题解 CF343C [Read Time]

Guess00

2019-11-16 11:30:39

题解

此时是2019.11.16,CSP-J第二试当天.据说考前发题解会rp++

先挂一下CF官方题解:

本题思路:二分答案

本题二分出最小满足要求的t,输出.

$\mathbb{A:}$枚举每个探头$,$在时间$t$内看TA最左能到哪一个要读的轨道$,$再看TA最右能到哪一个要读的轨道$.$若将$m$个轨道全覆盖了$,$说明满足要求$,$反之$,$不满足要求$.($看代码更好理解一点$)

时间复杂度:\Theta\big((n+m)\log_{2}\max(h[i],p[i])\big)

\text{注意}:$在判断时复杂度不是$nm,$而是$n+m.$在枚举可读到的轨道时是基于上一次的可到达的轨道$,$所以轨道只枚举了$m$次$. \mathbb{CODE:} 
#include <bits/stdc++.h>
#define int long long
#define MAXN 100005
#define inf 0x3f3f3f3f3f
int n,m,i,l,r=inf,mid,h[MAXN],p[MAXN];
inline void read(int &x)  //快读 
{
    short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
            negative=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
inline void print(int x)    //快输 
{
    if (x<0)
        putchar('-'),x=-x;
    if (x>9)
        print(x/10);
    putchar(x%10+'0');
}
inline int abs(int x){return x>0?x:-x;}
inline int min(int x,int y){return x<y?x:y;}
inline bool check(int t)     //本题重点:判断 
{
    int l,r,ans;
    l=r=1;
    for (i=1;i<=n;i++)
    {
        ans=abs(p[r]-p[l])+min(abs(p[l]-h[i]),abs(p[r]-h[i]));
        while (r<=m && ans<=t)  //枚举 
            r++,ans=abs(p[r]-p[l])+min(abs(p[l]-h[i]),abs(p[r]-h[i]));
        l=r;
        if (r>m)   //已经覆盖了所有轨道 
            return true;  //t满足要求 
    }
    return false;
}
signed main(void)
{
    read(n),read(m);   //输入 
    for (i=1;i<=n;i++)
        read(h[i]);
    for (i=1;i<=m;i++)
        read(p[i]); 
    while (l<=r)    //二分答案 
    {
        mid=(l+r)>>1;
        if (check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    print(l);   //愉快地输出 
    return 0;
}