0分求助

P1678 烦恼的高考志愿

Kirisama @ 2022-02-11 16:23:12

二分没学好,感觉思路对了,交上去一个没a,希望有大佬可以指导一下=_=

#include<bits/stdc++.h>
using namespace std;
int m,a[200000],n,b[200000],ans;
int check(int x,int y)
{
    if(x>=a[y]) return 1;
    else return 0;  
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+m);
    for(int i=1;i<=n;i++)
    {
        int l=1,r=n;
        scanf("%d",&b[i]);
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(b[i],mid)) l=mid+1;
            else r=mid;
        }
        ans+=min(abs(b[i]-a[l]),abs(b[i]-a[r]));
    }
    printf("%d",ans);
    return 0;
}

by 编码落寞 @ 2022-02-11 16:38:33

@ran_Diana

hack数据:

4 1

1 2 5 6

3

程序输出2

理论输出1


by 编码落寞 @ 2022-02-11 16:45:22

@ran_Diana

需要判断二分结束之后左右端点是否为同一值


by Kirisama @ 2022-02-11 16:52:02

@编码落寞 谢谢,已经解决了,是r值搞错了


|