P1678 烦恼的高考志愿

题目链接：

本题容易想到用二分进行优化，但其中有几个细节需要注意一下。

注意点1、特判

if (curr < a[0]) res += abs(curr - a[0]);

（该测试点为 \(m=1,n=100000\) 且所有数组元素全为 \(0\)）

2、可以二分出第一个 \(\geqslant b[i]\) 的数，则 \(\rm res\) 需要加的是 \(\rm abs(b[i]-a[l]\) 和 \(\rm abs(b[i]-a[l-1]\) 的最小值。

\(AC\) 代码：

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int N = 1e5 + 5;

int m, n;
int a[N], b[N];
LL res;

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]);
    sort(a, a + m);
    
    for (int i = 0; i < n; i++) {
        int curr = b[i], l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= curr) r = mid;
            else l = mid + 1;
        }
        if (curr < a[0]) res += abs(a[0] - curr);
        else res += min(abs(a[l] - curr), abs(a[l - 1] - curr));
    }
    printf("%lld", res);
    return 0;
}

3、类似地，可以二分出第一个 \(\leqslant b[i]\) 的数，则 \(\rm res\) 需要加的是 \(\rm abs(b[i]-a[l]\) 和 \(\rm abs(b[i]-a[l+1]\) 的最小值，需要分辨注意。

\(AC\) 代码：

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int N = 1e5 + 5;

int m, n;
int a[N], b[N];
LL res;

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) scanf("%d", &b[i]);
    sort(a, a + m);
    
    for (int i = 0; i < n; i++) {
        int curr = b[i], l = 0, r = m - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= curr) l = mid;
            else r = mid - 1;
        }
        if (curr < a[0]) res += abs(a[0] - curr);
        else res += min(abs(a[l] - curr), abs(a[l + 1] - curr));
    }
    printf("%lld", res);
    return 0;
}