描述高考结束了同学们要开始了紧张的填写志愿的过程大家希望找一个自己最满意的大学填报方案请你编程帮忙实现。现有mm≤100000所学校每所学校预计分数线是aiai≤106。有 nn≤100000位学生估分分别为 bibi≤106。根据n位学生的估分情况分别给每位学生推荐一所学校要求学校的预计分数线和学生的估分相差最小可高可低毕竟是估分嘛这个最小值为不满意度。求所有学生不满意度和的最小值。输入描述第一

思路：

首先，我们需要将学校的预计录取分数和学生的估分成绩进行排序，以便于后续的处理。

然后，我们使用双指针的方法，分别指向学校的预计录取分数和学生的估分成绩的数组的起始位置。

在遍历学生的估分成绩数组的过程中，我们将学校的预计录取分数与学生的估分成绩进行比较，如果学校的预计录取分数大于学生的估分成绩，则将学生推荐到该学校，并将不满意度加上学校的预计录取分数与学生的估分成绩的差值；如果学校的预计录取分数小于等于学生的估分成绩，则将学校的预计录取分数向后移动一位。

最后，输出所有学生的不满意度之和。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;

    vector<int> school(m);
    for (int i = 0; i < m; i++) {
        cin >> school[i];
    }

    vector<int> student(n);
    for (int i = 0; i < n; i++) {
        cin >> student[i];
    }

    sort(school.begin(), school.end());
    sort(student.begin(), student.end());

    int dissatisfaction = 0;
    int schoolIndex = 0;
    for (int i = 0; i < n; i++) {
        while (schoolIndex < m && school[schoolIndex] <= student[i]) {
            schoolIndex++;
        }
        if (schoolIndex < m) {
            dissatisfaction += abs(school[schoolIndex] - student[i]);
            schoolIndex++;
        }
        else {
            dissatisfaction += abs(school[m - 1] - student[i]);
        }
    }

    cout << dissatisfaction << endl;

    return 0;
}

时间复杂度分析：

排序学校的预计录取分数和学生的估分成绩的时间复杂度为O(mlogm + nlogn)。

遍历学生的估分成绩数组的时间复杂度为O(n)。

总的时间复杂度为O(mlogm + nlogn)。

空间复杂度分析：

除了输入和输出的空间，我们只额外使用了两个数组，所以空间复杂度为O(m + n)