P1678 烦恼的高考志愿

(图片即链接)

只需要对于每一个学生,找到使其股份与录取线的差最小的学校即可,所有差值之和即为答案.

通过把学校录取线排序后二分查找可以提高效率,这里的数据线性查找会爆.

将数组升序排列,使用upper_bound查找录取线不低于学生分数的第一个学校,则上一个学校低于学生分数,显然在这两者之间选择才会有最小差值,取min即可.

注意到当多个学校录取线相同时,这个算法也不会受到影响.

真正的关注点是边界情况:学生的分数低于所有录取线,和学生的分数高于所有录取线.

前者情况下upper_bound返回数组位置0,后者返回数组末尾之后第一个位置(即a[m],而数组末尾是a[m-1]).

这时处理起来仍然很简单.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n, m, a[100010], b[100010];
long long ans;

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) cin >> a[i];  // school m
    for (int i = 0; i < n; i++) cin >> b[i];  // student n
    sort(a, a + m);
//    m = unique(a, a + m) - a;　　// 后来才发现这里不需要去重

    for (int i = 0; i < n; i++) {
        int sad;
        int l = upper_bound(a, a + m, b[i]) - a - 1;
        int r = l + 1;
        if (l == m)　　　　// 特判
            sad = b[i] - a[m - 1];
        else if (l == -1)　　// 特判
            sad = a[0] - b[i];
        else
            sad = min(abs(b[i] - a[l]), abs(b[i] - a[r]));　　// 一般情况
        ans += sad;
    }

    cout << ans << endl;

    return 0;
}