用c++语言写以下程序:现有 m 所学校,每所学校预计分数线是 ai 。有 n 位学生,估分分别为 bi。 根据 n 位学生的估分情况,分别给每位学生推荐一所学校,要求学校的预计分数线和学生的估分相差最小(可高可低,毕竟是估分嘛),这个最小值为不满意度。求所有学生不满意度和的最小值。 输入格式 第一行读入两个整数 m,n。m表示学校数,n表示学生数。 第二行共有 m个数,表示 m个学校的预计录取分数。第三行有 n个数,表示 n个学生的估分成绩。 输出格式 输出一行,为最小的不满度之和。
时间: 2024-02-06 10:12:14 浏览: 37
以下是用 C++ 实现的程序:
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100010;
int m, n;
int a[N], b[N];
int main()
{
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); // 将学校分数线从小到大排序
sort(b, b + n); // 将学生估分从小到大排序
int res = 0;
for (int i = 0; i < n; i++)
{
// 找到学校分数线中第一个大于等于学生估分的位置
int j = lower_bound(a, a + m, b[i]) - a;
// 计算学生估分与学校分数线差值的绝对值
int d = abs(a[j] - b[i]);
if (j > 0) d = min(d, abs(a[j - 1] - b[i])); // 考虑学校分数线低于估分的情况
res += d; // 累计不满意度
}
cout << res << endl;
return 0;
}
```
程序思路:
首先,我们将学校的预计录取分数从小到大排序,将学生的估分成绩从小到大排序。
对于每个学生,我们找到学校分数线中第一个大于等于学生估分的位置,计算学生估分与学校分数线差值的绝对值,然后将其加入不满意度中。
需要考虑学校分数线低于估分的情况,这时我们还需要找到学校分数线中第一个小于学生估分的位置,计算其与学生估分的差值,取其与上一步计算结果的较小值。
最后,输出所有学生不满意度和的最小值。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)