B1899 【基础】最满意的方案
大约 3 分钟
B1899 【基础】最满意的方案
【算法】 二分查找
【C++】 二分查找、lower_bound、abs
【难度】 普及−
B1899 【基础】最满意的方案
一、题目简述
有 所学校的录取分数线 , 位学生的估分 。要为每位学生推荐一所分数线与学生估分最接近的学校(即 最小)。定义不满意度 = 学生估分与推荐学校分数线的差值的绝对值。求所有学生的不满意度之和的最小值。
数据范围:,分数线与估分均 。
二、解题思路
数据规模分析
和 都是 级别。如果对每个学生的估分都遍历所有学校找最接近的分数线,复杂度 会超时。
算法选择
先对学校分数线排序(),然后对每位学生的估分 ,用二分查找在排序后的分数线中找到与其最接近的值。
具体做法:
- 使用
lower_bound找到第一个 的分数线位置 - 真正最接近的分数线只可能在 或者 中(如果这两个位置都合法存在的话)
- 比较
|a[pos] - b_i|和|a[pos-1] - b_i|,取较小值累加到答案
这就是典型的一维最近邻搜索问题,排序后二分即可解决。
手动模拟
假设学校分数线:,学生估分:。
对 :
lower_bound找到 ( 是第一个 的)。比较:- ,差值
- ,差值
- 取最小差值
对 :
lower_bound找到 ()。比较:- ,差值
- ,差值
- 取最小差值
对 :
lower_bound找到 (超出数组范围,只有 合法)。比较:- ,差值
- 取最小差值
不满意度之和:。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N];
int main() {
int m, n;
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
// 对学校分数线排序
sort(a + 1, a + m + 1);
long long ans = 0;
for (int i = 1; i <= n; i++) {
int pos = lower_bound(a + 1, a + m + 1, b[i]) - a;
int best = 2e9; // 初始化为一个很大的数
// 检查 a[pos](如果存在)
if (pos <= m) best = min(best, abs(a[pos] - b[i]));
// 检查 a[pos-1](如果存在)
if (pos > 1) best = min(best, abs(a[pos - 1] - b[i]));
ans += best;
}
printf("%lld\n", ans);
return 0;
}四、复杂度分析
- 时间复杂度:排序 , 次二分查找 。总复杂度 。
- 空间复杂度:两个静态数组 。
五、知识扩展
为什么只检查 a[pos] 和 a[pos-1]?
排序后的数组是单调递增的。lower_bound 返回的位置 满足:
- 所有 ,有 (严格小于)
- 所有 ,有
因此 落在区间 之间(如果两端都存在)。距离 最近的点必然是这个区间的端点之一,无需检查更远的点。
边界处理
用 pos <= m 和 pos > 1 优雅地处理了边界情况。best 初始化为一个很大的值(如 ),确保至少有一个合法的差值被选入。
