高考志愿填报方案推荐算法：最小不满意度之和

高考结束了，同学们要开始了紧张的填写志愿的过程，大家希望找一个自己最满意的大学填报方案。本文将介绍一种使用双指针算法解决高考志愿填报方案推荐问题的方案，旨在帮助学生找到最符合其估分情况的大学，并最小化所有学生的不满意度之和。

问题描述

现有m(m≤100000)所学校，每所学校预计分数线是ai(ai≤106)。有 n(n≤100000)位学生，估分分别为 bi(bi≤106)。

根据n位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入描述

第一行读入两个整数m,n。m表示学校数，n表示学生数。第二行共有m个数，表示m个学校的预计录取分数。第三行有n个数，表示n个学生的估分成绩。

输出描述

一行，为最小的不满度之和。（数据保证结果<=1010）

算法思路

排序: 首先，我们需要将学校的预计录取分数和学生的估分成绩进行排序，以便于后续的处理。
双指针: 然后，我们使用双指针的方法，分别指向学校的预计录取分数和学生的估分成绩的数组的起始位置。
遍历: 在遍历学生的估分成绩数组的过程中，我们将学校的预计录取分数与学生的估分成绩进行比较，如果学校的预计录取分数大于学生的估分成绩，则将学生推荐到该学校，并将不满意度加上学校的预计录取分数与学生的估分成绩的差值；如果学校的预计录取分数小于等于学生的估分成绩，则将学校的预计录取分数向后移动一位。
计算: 最后，输出所有学生的不满意度之和。

代码实现 (C++)

#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)。

总结

本文介绍了一种使用双指针算法解决高考志愿填报方案推荐问题的方案，该方案能够在较短的时间内找到最符合学生估分情况的大学，并最小化所有学生的不满意度之和。希望本文能够帮助同学们找到合适的大学，顺利填报志愿！