1
2
3

4 3
513 598 567 689
500 600 550

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <algorithm> // 包含 std::sort 与 std::lower_bound
#include <cmath>     // 包含 std::abs 用于计算绝对值差
#include <iostream>  // 包含 std::cin 与 std::cout 输入输出
#include <vector>    // 包含 std::vector 动态数组

using namespace std;

int main() {
    // 关闭 cin/cout 与 C 标准输入输出的同步，解除 cin 与 cout 的绑定
    // 在处理 N, M 可达 10^5 的大量数据输入输出时，显著提升读写效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    // 读取学校数量 m 与学生数量 n
    if (!(cin >> m >> n)) return 0;

    // 创建大小为 m 的数组，保存 m 所学校的预计分数线
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    // 1. 对学校预计分数线进行升序排序
    // 二分查找的前提条件必须是序列具有单调性（有序）
    sort(a.begin(), a.end());

    // 2. 累计所有学生的不满意度
    // 注意：所有学生不满意度的最大可能总和为 10^5 * 10^6 = 10^11，
    // 超过了 32 位 int 的最大值 (~2.14 * 10^9)，因此必须使用 64 位 long long
    long long total_dissatisfaction = 0;

    // 3. 逐个读入每位学生的估分并进行二分查找
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b; // 读取第 i 位学生的估分

        // std::lower_bound 用于在升序区间 [a.begin(), a.end()) 内
        // 查找第一个大于等于估分 b 的学校分数线迭代器
        auto it = lower_bound(a.begin(), a.end(), b);
        // 通过 std::distance 计算该迭代器在 vector 中的下标位置 [0, m]
        int pos = distance(a.begin(), it);

        if (pos == 0) {
            // 情况一：学生估分 b 比所有学校的分数线都低
            // 最近的学校只能是最低录取线 a[0]，注意不能访问 a[-1]
            total_dissatisfaction += abs(a[0] - b);
        } else if (pos == m) {
            // 情况二：学生估分 b 比所有学校的分数线都高
            // lower_bound 返回 a.end()，下标 pos 为 m
            // 最近的学校只能是最高录取线 a[m - 1]
            total_dissatisfaction += abs(a[m - 1] - b);
        } else {
            // 情况三：学生估分 b 介于 a[pos-1] 与 a[pos] 之间
            // 离 b 最近的分数线必在小于等于 b 的最大值 a[pos-1]
            // 和大于等于 b 的最小值 a[pos] 之中产生
            int diff1 = abs(a[pos] - b);     // 计算与右侧大于等于 b 的学校的绝对差
            int diff2 = abs(a[pos - 1] - b); // 计算与左侧小于 b 的学校的绝对差
            total_dissatisfaction += min(diff1, diff2); // 取两者中的较小差值
        }
    }

    // 4. 输出所有学生最小不满意度的总和
    cout << total_dissatisfaction << "\n";

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <algorithm> // 包含 std::sort
#include <cmath>     // 包含 std::abs
#include <iostream>  // 包含 std::cin 与 std::cout
#include <vector>    // 包含 std::vector

using namespace std;

/**
 * @brief 手写二分查找函数（等价于 std::lower_bound）
 * 
 * @param a 已排好序的升序数组
 * @param target 目标查找值（学生的估分 b）
 * @return int 第一个大于等于 target 的元素下标；若不存在则返回 a.size()
 */
int my_lower_bound(const vector<int>& a, int target) {
    int left = 0;
    int right = a.size() - 1;
    int ans = a.size(); // 初始值设为 a.size()，表示若所有元素都比 target 小时的默认返回值

    // 循环条件：左边界不超过右边界
    while (left <= right) {
        // 计算中间位置，采用 left + (right - left) / 2 可以防止 (left + right) 直接相加导致的数值溢出
        int mid = left + (right - left) / 2;

        if (a[mid] >= target) {
            ans = mid;       // 记录当前满足 >= target 的候选位置
            right = mid - 1; // 尝试在更左侧的区间寻找是否还有更靠前的合法位置
        } else {
            left = mid + 1;  // 当前值 a[mid] 小于 target，说明目标位置一定在 mid 右侧
        }
    }
    return ans; // 返回最终找到的第一个 >= target 的元素下标
}

int main() {
    // 快速输入输出优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;

    // 读入 m 所学校录取线
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    // 1. 对学校录取线进行升序排序
    sort(a.begin(), a.end());

    // 2. 初始化总不满意度，必须为 long long 类型（防止累加溢出）
    long long total_dissatisfaction = 0;

    // 3. 处理每个学生的估分
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;

        // 使用手写的二分查找算法定位第一个大于等于 b 的学校下标 pos
        int pos = my_lower_bound(a, b);

        if (pos == 0) {
            // 下标为 0：估分低过所有学校，取录取线最低的学校 a[0]
            total_dissatisfaction += abs(a[0] - b);
        } else if (pos == m) {
            // 下标为 m：估分高过所有学校，取录取线最高的学校 a[m - 1]
            total_dissatisfaction += abs(a[m - 1] - b);
        } else {
            // 下标在 (0, m) 范围内：比较左侧 a[pos-1] 和右侧 a[pos]，累加较小绝对差
            int diff_right = abs(a[pos] - b);
            int diff_left = abs(a[pos - 1] - b);
            total_dissatisfaction += min(diff_right, diff_left);
        }
    }

    // 4. 输出答案
    cout << total_dissatisfaction << "\n";

    return 0;
}