首页 > 代码库 > Data

Data

技术分享

技术分享技术分享

【pdf你真可爱】

【题目分析】

  上午考试想到用二分答案做,写残了...

  设两个数列,a和b,a表示磁头,看作指针,b就是要扫描的那个序列。

  假设一个答案mid,就是a中的数字走mid步能否到达b中的数字,如果b能全部被扫描,说明这个答案是可以继续向左二分,否则就向右

  具体就分三种情况:

  1、a[i]-b[j]>mid,这种情况下怎么走都不可能把b完全覆盖(因为a和b都是递增的,前面的只要大于了,后面没有机会变小于啊),直接false

  2、a[i]>b[j],rest表示从a[i]扫到b[j]之后剩余的,rest=mid-(a[i]-b[j])

 

    (1)先走左边,reach=b[j]+rest

    技术分享

    (2)先走右边,reach=a[i]+rest/2;

    技术分享

  3、a[i]<=b[j],那从a[i]开始扫,最多扫到 reach=a[i]+mid

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define ll long long const int maxn=1e5+10;int n,m;ll a[maxn],b[maxn];bool check(ll mid){    for(ll i=1,j=1;i<=n;i++)    {        if(a[i]-b[j]>mid) return false;//如果从i到j的距离比假设的答案大,就返回0继续向右二分        ll reach;//reach表示走完mid步之后到达的位置         if(a[i]>b[j])        {            ll rest=mid-(a[i]-b[j]);            reach=max(b[j]+rest,a[i]+rest/2);//向左边走和向右边走         }        else            reach=a[i]+mid;        while(b[j]<=reach&&j<=m) j++;        if(j>m) return true;     }    return false;}void solve(){    ll l=0,r=1e10,ans;    while(l<=r)    {        ll mid=(l+r)/2;        if(check(mid)) r=mid-1,ans=mid;        else l=mid+1;    }    printf("%I64d",ans);}int main(){    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)        scanf("%I64d",&a[i]);    for(int i=1;i<=m;i++)        scanf("%I64d",&b[i]);    /*int flag=0;    if(n==m)    {        for(int i=1;i<=n;i++)            if(a[i]!=b[i])                flag=1;    }    if(flag==0&&n==m)        printf("0");    else    {*/        solve();    //}    fclose(stdin);fclose(stdout);    return 0;}

 

Data