【题目来源】
洛谷：P1678 烦恼的高考志愿 - 洛谷
【题目描述】
现有 \(m\) 所学校，每所学校预计分数线是 \(a_i\)。有 \(n\) 位学生，估分分别为 \(b_i\)。
根据 \(n\) 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。
【输入】
第一行读入两个整数 \(m,n\)。\(m\) 表示学校数，\(n\) 表示学生数。
第二行共有 \(m\) 个数，表示 \(m\) 个学校的预计录取分数。第三行有 \(n\) 个数，表示 \(n\) 个学生的估分成绩。
【输出】
输出一行，为最小的不满度之和。
【输入样例】
4 3
513 598 567 689
500 600 550
【输出样例】
32
【解题思路】
【算法标签】
《洛谷 P1678 烦恼的高考志愿》 #模拟# #贪心# #二分# #排序#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// m: 仓库数量
// n: 商店数量
// a[100005]: 存储仓库位置
// b[100005]: 存储商店位置
// ans: 存储总运输成本
int m, n, a[100005], b[100005];
long long ans = 0;int main()
{// 输入仓库数量和商店数量cin >> m >> n;// 输入仓库位置for (int i = 0; i < m; i++){cin >> a[i];}// 对仓库位置进行排序sort(a, a + m);// 处理每个商店的运输需求for (int i = 0; i < n; i++){cin >> b[i]; // 输入商店位置// 情况1：商店在最左侧仓库的左边if (a[0] > b[i]){ans += a[0] - b[i]; // 运输到第一个仓库}// 情况2：商店在最右侧仓库的右边else if (a[m - 1] < b[i]){ans += b[i] - a[m - 1]; // 运输到最后一个仓库}// 情况3：商店位于两个仓库之间else{// 使用二分查找找到第一个不小于商店位置的仓库int k = lower_bound(a, a + m, b[i]) - a;// 计算到左右两个仓库的最小距离ans += min(b[i] - a[k - 1], a[k] - b[i]);}}// 输出总运输成本cout << ans << endl;return 0;
}
【运行结果】
4 3
513 598 567 689
500 600 550
32