又是我来求助了,神犇们捞捞

P1678 烦恼的高考志愿

Megumimwf @ 2023-01-18 09:07:39

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0, f = 1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while(ch>='0' && ch<='9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
bool flag;
long long ans;
int q, l, r, mid, n, m, sch[100086], stu[100086];
int main() {
    n = read();
    m = read();
    for(int i=1; i<=n; ++i) {
        sch[i] = read();
    }   
    for(int i=1; i<=m; ++i) {
        stu[i] = read();
    }
    sort(sch+1, sch+1+n);
    for(int i=1; i<=m; ++i) {
        q = stu[i];
        if(q <= sch[1]) {
            ans += sch[1] - q;
            continue;
        } else if(q >= sch[n]) {
            ans += q - sch[n];
            continue;
        }
        flag = false;
        l = 1;
        r = m;
        while(l < r) {
            mid = (l + r)/2;
            if(q == sch[mid]) {
                flag = true;
                break;
            } else if(q < sch[mid]) {
                r = mid;
            } else if(q > sch[mid]) {
                l = mid + 1;
            }
        }
        if(flag) {
            continue;
        }
        if(abs(sch[l-1]-q) < abs(sch[l]-q)) {
            ans += abs(sch[l-1]-q);
        } else {
            ans += abs(sch[l]-q);
        }
    }
    printf("%lld", ans);
    return 0;
}

|