烦恼的高考志愿

思路：要为学生分配学校，所以找与学生预估成绩相近的学校分数，因为最外层循环遍历学生成绩。然后用学生成绩对比，进行二分，找到最小的大于预估成绩的学校分数，但不能确定它们之间的不满意度最小，所以还要拿比这个学校分数更小一点的去比，这样才能得出最小不满意度。注意：如果二分的结果为0，就没有分数更小的学校，所以要特判，在l == 0时，直接计算即可，即：d = abs(s[i) - c[l])

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

题目描述

现有 $m$ 所学校，每所学校预计分数线是 $a_i$。有 $n$ 位学生，估分分别为 $b_i$。

根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 $m,n$。$m$ 表示学校数，$n$ 表示学生数。

第二行共有 $m$ 个数，表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

样例 #1

样例输入 #1

4 3
513 598 567 689
500 600 550

样例输出 #1

32

提示

数据范围：

对于 $30\%$ 的数据，$1\leq n,m\leq1000$，估分和录取线 $\leq10000$；

对于 $100\%$ 的数据，$1\leq n,m\leq100000$，估分和录取线 $\leq 1000000$ 且均为非负整数。

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;

typedef long long LL;

const int N = 100010;
int n, m;
int s[N], c[N];

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) scanf("%d", &c[i]);
    for (int i = 0; i < n; i++) scanf("%d", &s[i]);

    LL ans = 0;
    sort(s, s + n);
    sort(c, c + m);
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = m - 1;
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (c[mid] >= s[i]) r = mid;
            else l = mid + 1;
        }
        int d = min(abs(s[i] - c[l]), abs(s[i] - c[l - 1]));
        //如果l == 0,就不能算s[i] - c[l - 1]，这样最小值一直是0，所以要特判
        if (l == 0) d = abs(s[i] - c[l]);
        ans += d;
    }

    printf("%lld", ans);

    return 0;
}