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

一、题目理解输入第一行、m所学校n位学生第二行、m个预计录取分数第三行、n个学生估分成绩输出最小不满意度之和二、解题思路其实这题就是简单的二分对于我这种菜鸟来说咱就用最简单最好理解的方式来写。1、首先观察一下数据范围把全局变量写出来。注定义在主函数外的原因避免栈溢出。局部变量存储在栈区课件大小有限全局变量存储在数据短空间更大。默认初始化为0数组和变量都是。2、要想求所有学生的差值和最小要先求每个学生的最小差值然后累加所以我们需要先对m个学校预估的分数进行从小到大排序然后针对每个学生的成绩进行二分查找找到最接近的分数线。三、代码解析#include iostream #include algorithm //sort函数算法库 #include cmath //数学库abs绝对值 using namespace std;头文件用万能头文件最好#includebits/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]; // 学校和学生估计分数观察数据mn范围都是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用来记住二分返回的结果也就是左端点值其实右端点也一样因为循环停止的条件是lr。初始l0, r4, 区间 [0,4)第1轮mid 0 (4-0)/2 2arr[2]598 550? 是r mid 2区间变为 [0,2)第2轮mid 0 (2-0)/2 1arr[1]567 550? 是r mid 1区间变为 [0,1)第3轮mid 0 (1-0)/2 0arr[0]513 550? 否l mid 1 1区间变为 [1,1)此时 l1, r1循环结束 (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| 37a[0]513: |513-530| 17 ← 更接近最接近的是 a[0]513差值17所以有可能前面的更接近。排序后的数组: [..., a[pos-1], a[pos], ...]↑ ↑小于估分 大于等于估分↓ ↓估分在这里中间估分位置pos值检查pos检查pos-1结果小于所有0✅ (a[0])❌ (越界)只检查第一个在中间1~m-1✅ (a[pos])✅ (a[pos-1])比较两个大于所有m❌ (越界)✅ (a[m-1])只检查最后一个最后进行累加输出就行最后的最后小编有话说这是本人star的第一篇博客还希望各位大佬轻点喷也欢迎各位大佬指出宝贵的建议见证star的成长咱们下篇见