不用二分的方法怎么写?我已经70分,还有3个错.

dfydada⚡⚡⚡ @ 2019-08-14 14:55:08

#include<bits/stdc++.h>
//#pragma GCC optimize(2)//O2优化
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=200000+10;
ll n,m;
ll tot,ans,ant,any,num;
struct asd
{
    ll x,y;
}a[N];
ll read()
{
    ll res=0,chr=getchar(),st=1;
    if(chr=='-')
    {
        st=-1;
    }
    while(!isdigit(chr)&&chr!=EOF)
    {
        chr=getchar();
    }
    while(isdigit(chr))
    {
        res=(res*10)+(chr-'0');
        chr=getchar();
    }
    return res*st;
}
bool bll(asd l,asd r)
{
    return l.x<r.x;
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        tot++;
        a[tot].x=read();
    }
    for(int i=1;i<=m;i++)
    {
        tot++;
        a[tot].x=read();
        a[tot].y=1;
    }
    sort(a+1,a+1+tot,bll);
    for(int i=1;i<=tot;i++)
    {
        if(a[i].y!=1)
        {
            ans=a[i].x;
        }
        else
        {
            if(i<=ant)
            {
                num+=min(abs(ans-a[i].x),abs(any-a[i].x));
            }
            else
            {
                ant=i;
                while(ant<=tot)
                {
                    ant++;
                    if(a[ant].y!=1)
                    {
                        any=a[ant].x;
                        break;
                    }
                }
                num+=min(abs(ans-a[i].x),abs(any-a[i].x));
            }
        }
    }
    cout<<num;
    return 0;
}

by dfydada⚡⚡⚡ @ 2019-08-14 14:56:07

这是那3个错的点

by K2sen @ 2019-08-14 15:09:50

不用二分，可以用lower_bound和upper_bound

by dfydada⚡⚡⚡ @ 2019-08-14 15:14:59

@Morbid 我错那了?求解

by K2sen @ 2019-08-14 15:21:32

@dfydada 看不懂您的代码...

by K2sen @ 2019-08-14 15:28:36

@dfydada 您还是用二分吧，你的代码我没看懂，然后可以用lower_bound 和 insert 来存然后用lower_bound 和 upper_bound找出比这个分数小的和大的第一个数，然后比较差值的绝对值大小...

by dfydada⚡⚡⚡ @ 2019-08-14 15:31:05

@Morbid 我也是找比这个分数小的和大的第一个数，然后比较差值的绝对值大小

by dfydada⚡⚡⚡ @ 2019-08-14 15:32:16

#include<bits/stdc++.h>
//#pragma GCC optimize(2)//O2优化
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=200000+10;
ll n,m;
ll tot,ans,ant,any,ams,num;
struct asd
{
    ll x,y;
}a[N];
ll read()
{
    ll res=0,chr=getchar(),st=1;
    if(chr=='-')
    {
        st=-1;
    }
    while(!isdigit(chr)&&chr!=EOF)
    {
        chr=getchar();
    }
    while(isdigit(chr))
    {
        res=(res*10)+(chr-'0');
        chr=getchar();
    }
    return res*st;
}
bool bll(asd l,asd r)
{
    return l.x<r.x;
}
int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        tot++;
        a[tot].x=read();
    }
    for(int i=1;i<=m;i++)
    {
        tot++;
        a[tot].x=read();
        a[tot].y=1;//估分和入取分一起排序 
    }
    sort(a+1,a+1+tot,bll);
    for(int i=1;i<=tot;i++)
    {
        if(a[i].y!=1)
        {
            ans=a[i].x;//这个为估分前面一个入取分 
        }
        else
        {
            if(i<=ams)//如果ams大于说明之前已经找过一个在现在估分后面的入取分了,就不用在找 
            {
                num+=min(abs(ans-a[i].x),abs(any-a[i].x));
            }
            else//否者就说明没找到,或者之前找到的比现在的小 
            {
                ant=i;//从i开始,继续找 
                while(ant<=tot)
                {
                    ant++;
                    if(a[ant].y!=1)
                    {
                        any=a[ant].x;
                        ams=ant;//这里不一定找到了后面的点,如果找到了就没用一个变量在存下标 
                        break;
                    }
                }
                num+=min(abs(ans-a[i].x),abs(any-a[i].x));
            }
        }
    }
    cout<<num;
    return 0;
}

by dfydada⚡⚡⚡ @ 2019-08-14 15:33:00

@Morbid 我只是没用lower_bound 和 upper_bound(不会)

by K2sen @ 2019-08-14 16:05:11

@dfydada 可以自学啊...

by dfydada⚡⚡⚡ @ 2019-08-14 16:14:00

...