二分。。TLE*2？！

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 15:53:00

后面那一堆判断语句没必要吧。

by SZnP @ 2022-12-11 15:59:58

@2124Kobe 我删掉试试

好像并没有什么用的样子

#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;}
        ans+=min(abs(score[i]-line[mid]),abs(line[mid+1]-score[i]));
    }
    cout<<ans;

    return 0;
}

by Kevin_Mamba @ 2022-12-11 16:07:26

@SZnP

lower_bound 了解一下。

    line[m+1]=0x7fffffff;
    line[0]=-line[m+1];
//    m+=2;
    sort(line+1,line+m+1);//<
    for(int i=0;i<n;i++)
    {
        int k=lower_bound(line,line+m+1,score[i])-line;
        ans+=min(abs(score[i]-line[k]),abs(score[i]-line[k-1]));
    }
    cout<<ans;

by Kevin_Mamba @ 2022-12-11 16:07:56

等等，我去改下下你的。

by Kevin_Mamba @ 2022-12-11 16:14:20

@SZnP

#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);//<
    line[0]=-line[m+1];
    for(int i=0;i<n;i++)
    {
        l=0;r=m-1;
        getans=0;
        while(l+1<r)
        {
            mid=l+(r-l)/2;
//            if(line[mid]<=score[i]&&line[mid+1]>=score[i]){getans=1;break;}
            if(line[mid]>score[i])r=mid;
            else l=mid;
        }
//        if(getans==1&&mid==0){ans+=abs(score[i]-line[1]);continue;}
        ans+=min(abs(score[i]-line[l]),abs(line[r]-score[i]));
    }
    cout<<ans;

    return 0;
}

by SZnP @ 2022-12-11 16:14:43

@2124Kobe tql

by Kevin_Mamba @ 2022-12-11 16:15:35

二分时不要想的太复杂。

大了就 r=mid，否则 l=mid 。

by SZnP @ 2022-12-11 16:16:58

@2124Kobe 好吧，

by Kevin_Mamba @ 2022-12-11 16:17:22

而且建议记一下模板。

1. while(l+1<r)

l=mid; r=mid;

2. while(l<=r)

l=mid+1; r=mid-1;

这两个比较好记。

by SZnP @ 2022-12-11 16:18:35

@2124Kobe why l+1<r ?