二分。。TLE*2?!

P1678 烦恼的高考志愿

SZnP @ 2022-12-11 15:37:43

好吧就是求调

#include <bits/stdc++.h>
using namespace std;
long long line[100010],score[100010],n,m,ans,l,r,mid;
int getans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m>>n;
    for (int i = 1; i <=m; i++)
        cin>>line[i];
    for(int i=0;i<n;i++)
        cin>>score[i];
    line[m+1]=0x7fffffff;
    m+=2;
    sort(line,line+m);//<
    for(int i=0;i<n;i++)
    {
        l=0;r=m-2;
        getans=0;
        while(r>=l)
        {
            mid=l+(r-l)/2;
            if(line[mid]<=score[i]&&line[mid+1]>=score[i]){getans=1;break;}
            else if(line[mid]>score[i])r=mid;
            else l=mid;
        }
        if(getans==1&&mid==0){ans+=abs(score[i]-line[1]);continue;}
        if(getans==1&&mid==m-2){ans+=abs(score[i]-line[mid-1]);continue;}
        if(getans==1)ans+=min(abs(score[i]-line[mid]),abs(line[mid+1]-score[i]));
        else ans+=min(abs(line[mid]-score[i]),abs(score[i]-line[mid-1]));
    }
    cout<<ans;

    return 0;
}

by Kevin_Mamba @ 2022-12-11 16:21:06

@SZnP 不知道,有段时间了,忘记老师怎么讲的了。


by SZnP @ 2022-12-11 16:21:32

@2124Kobe 好吧,thx%%%


上一页 |