题解 | 烦恼的高考志愿

原题链接(ACGO):A8023.烦恼的高考志愿、
原题链接(洛谷):P1678.烦恼的高考志愿

整体思路

思维量$\color{orange}普及-$（中位） 码量 $\color{yellow}普及/提高-$ （下位）
废话不多说，这道题正解应该使用二分，通过分治一步步逼近最优答案，并使用变量储存，最后将每个人的不满意值合并。

详细步骤

• 输入数据，排序大学预期分数线
• 循环枚举每个人，求每一部分的不满意度
• 使用res变量逐步记录最小不满意值，二分逼近最优解
• 将每个人的最小不满意值合并求解

代码(AC)

#include <bits/stdc++.h>
#define int long long
//全局开long long
using namespace std;
const int MAXN = 100005;
int m,n,a[MAXN],b[MAXN],ans;
signed main(){
    cin >> m >> n;
    for(int i = 1;i <= m;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++) cin >> b[i];
    sort(a+1,a+m+1);
    sort(b+1,b+n+1);
    for(int i = 1;i <= n;i ++){
        int l = 1,r = m,mid,res=1e9;//res存放每个人的不满意度
        while(l <= r){
            mid = (l+r)/2;
            if(a[mid] == b[i]){//相等就是不满意度最小
                res = 0;
                break;
            }
            if(a[mid] < b[i]){
                l = mid+1;
                res = min(res,b[i] - a[mid]);//求不满意值，是不是最小的
            }
            if(a[mid] > b[i]){
                r = mid-1;
                res = min(res,a[mid] - b[i]);//同上
            }
        }
        ans += res;//加上步骤最优解
    }
    cout << ans;
    return 0;
}

评估

预期得分:$100pts$
实际得分:$100pts$
时间复杂度:$O(n\log n)$
空间复杂度:$O(n)$

感谢您的观看

$\operatorname{upd:}$ 2025.4.26撰写本篇文章