求助，二分70分

P1678 烦恼的高考志愿

waioi_lin @ 2022-11-18 20:23:36

#include "cstdio"
#include "algorithm"
#include "cmath"
#define LL long long
using namespace std;

int in()
{
    char c=getchar();
    int x=0,f=1;
    for(;c<'0' || c>'9';c=getchar())
        if(c=='-') f=-1;
    for(;c>='0' && c<='9';c=getchar())  
        x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}

const int N=100005;
int a[N], b[N];
int m, n, now;

int main()
{
    // freopen("P1678_1.in","r",stdin);
    // freopen("P1678_1.ans","w",stdout);
    m=in(), n=in();
    for(int i=1;i<=m;i++)   
        a[i]=in();//预计录取分数
    for(int i=1;i<=n;i++)
        b[i]=in();//估分成绩
    LL ans=0;
    sort(a+1,a+m+1);
    for(int i=1;i<=n;i++)
    {
        now=lower_bound(a+1,a+1+m,b[i])-a;
        ans+=min(abs(a[now]-b[i]), abs(a[now-1]-b[i]));
    }
    printf("%lld\n", ans);
    return 0;
}

by A350_ti @ 2022-11-18 20:51:33

没判边界情况，应该是这样

    for(int i=1;i<=n;i++)
    {
        now=lower_bound(a+1,a+1+m,b[i])-a;
        if(now==m+1){
            ans+=b[i]-a[m];
        }
        else{
            if(now==1){
                ans+=a[1]-b[i];
            }
            else ans+=min(abs(a[now]-b[i]), abs(a[now-1]-b[i]));
        }

    }

by waioi_lin @ 2022-11-18 20:55:09

@A350_ti 谢谢，过了

by sunfish @ 2023-03-08 00:40:13

@A350_ti 请问为什么要判断边界呢？如果是学校分都小于第i位学生的分，lower(first,last,b[i])此时会返回last，a[last]=0,a[last-1]与b[i]的差绝对值一定小于a[last]与b[i]差的绝对值，而last-1值就是我们所需要的，有什么判断的必要吗？同理为什么要判断上边界呢，返回的first不就是所需要的地址吗？卡在这好久，实在想不出为什么，望大佬解答

by sunfish @ 2023-03-08 01:24:10

@sunfish 突然想通了，是因为now-1：当返回first的时候b[now-1]成了b[0]，所以才会出现问题！上界应该是无需判断的