洛谷P1678烦恼的高考志愿题解

一、题目理解

输入：第一行、m所学校，n位学生

第二行、m个预计录取分数

第三行、n个学生估分成绩

输出：最小不满意度之和

二、解题思路

其实这题就是简单的二分，对于我这种菜鸟来说，咱就用最简单最好理解的方式来写。

1、首先观察一下数据范围，把全局变量写出来。

注：定义在主函数外的原因

• 避免栈溢出。

局部变量存储在栈区，课件大小有限，全局变量存储在数据短，空间更大。

• 默认初始化为0，数组和变量都是。

2、要想求所有学生的差值和最小，要先求每个学生的最小差值然后累加，所以我们需要先对m个学校预估的分数进行从小到大排序，然后针对每个学生的成绩进行二分查找找到最接近的分数线。

三、代码解析

#include <iostream> #include <algorithm> //sort函数，算法库 #include <cmath> //数学库，abs绝对值 using namespace std;

头文件用万能头文件最好#include<bits/stdc++.h>，但是Mac系统用不了devc++，所以我用vscode写，后面博客将全是用到啥头文件写啥。

• #include <algorithm>：算法库，提供sort（排序）和lower_bound（二分查找）

• #include <cmath>：数学库，提供abs（绝对值函数）

• using namespace std;：使用标准命名空间，避免写std::前缀

const int N = 100010; // m,n大小最大为10的5次方，开的稍微大一点 int a[N], b[N]; // 学校和学生估计分数

• 观察数据m，n范围，都是10的5次方，所以我们定义N稍大为100010.
• a[N]数组放m个学校的预估分数，b[N]数组放n个学生的预计成绩

int erfen(int arr[], int l, int r, int t) { while (l < r) { int mid = l + (r - l) / 2; // 防止溢出 if (arr[mid] >= t) { r = mid; } else l = mid + 1; } return l; }

定义二分函数

• 我们需要知道二分数组arr[]、查找的区间l,r、和查找的数t。
• int mid = l + (r - l) / 2; 为了防止溢出可以这么求mid，当然也可以用移位运算符

  int mid = l + ((r - l) >> 1);但得注意加上括号。

int main() { int m, n; cin >> m >> n; for (int i = 0; i < m; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; } sort(a, a + m); // 对学校预计分数进行从小到大排序 long long sum = 0; // sum可能超int

主函数部分

• 三行输入：m,n和两个数组。
• 直接用sort函数对a数组排列，当然你也可以手写排序，各种排序方法都可以。
• sum用来存储输出结果不满意度和，因为 m 和 n 最大 10^5，差值最大 10^6，最坏情况总和可能达到 10^11，超过int范围（约 2×10^9）所以要用long long。

for (int i = 0; i < n; i++) { int score = b[i]; int pos = erfen(a, 0, m, score); int diff = 2e9; // diff记录当前学生与学校分数差最小值，所以初始化为最大 if (pos < m) { diff = min(diff, abs(a[pos] - score)); } if (pos > 0) { diff = min(diff, abs(a[pos - 1] - score)); } sum += diff; } cout << sum << endl; return 0; }

• for循环里先遍历每个学生的成绩，然后对每个成绩进行二分查找，找到第一个>=学生估分的位置，pos用来记住二分返回的结果，也就是左端点值（其实右端点也一样，因为循环停止的条件是l==r）。

初始：l=0, r=4, 区间 [0,4)

第1轮：
mid = 0 + (4-0)/2 = 2
arr[2]=598 >= 550? 是
r = mid = 2
区间变为 [0,2)

第2轮：
mid = 0 + (2-0)/2 = 1
arr[1]=567 >= 550? 是
r = mid = 1
区间变为 [0,1)

第3轮：
mid = 0 + (1-0)/2 = 0
arr[0]=513 >= 550? 否
l = mid + 1 = 1
区间变为 [1,1)

此时 l=1, r=1，循环结束 (l < r 不成立)

返回 l = 1 ✅

• 因为diff为记录当前该学生的差值最小值，所以初始化diff为一个很大的值2e9

重点：为什么要对pos进行大于0小于m的检查？

因为要保证不越界，而且第一个大于学生分数的学校分数不一定是差值最小，但是由于数组有序性，所以最小差值不是a[pos]就是a[pos-1]，所以要进行两次比较后再累加。

下面以一个例子来讲：

学校分数线: [513, 567, 598, 689]
学生估分: 530

二分查找:
erfen(...) 返回 pos = 1 (a[1]=567)

检查差值:
a[1]=567: |567-530| = 37
a[0]=513: |513-530| = 17 ← 更接近！

最接近的是 a[0]=513，差值17，所以有可能前面的更接近。

排序后的数组: [..., a[pos-1], a[pos], ...]
↑ ↑
小于估分 大于等于估分
↓ ↓
估分在这里中间

• 最后进行累加输出就行

最后的最后，小编有话说：这是本人star的第一篇博客，还希望各位大佬轻点喷，也欢迎各位大佬指出宝贵的建议，见证star的成长！咱们下篇见～