P1678 烦恼的高考志愿 题解

题目：P1678 烦恼的高考志愿

思路

题目要我们输出的是不满意度的最小值

总的来说，这道题要用到二分查找的思路

首先输入每一所学校的预计录取分数线以及每一位同学的估分成绩，然后将左哨兵和右哨兵的值设为-2e6和2e6，这样无论如何，b[i]都不会离这两个数更近

接下来就是二分查找，但是现在我们的分不一定完全相同，所以此时l和r的目的是找到a数组中离b[i]最近的两个数。算完之后再求出两个数哪个离b[i]最近(要求出绝对值哦)，然后记录不满意度最小的变量加上这个差值

最后输出不满意度的最小值

重难点

如何用二分查找来找到不满意度的最小值

代码

#include <bits/stdc++.h>
using namespace std;

int a[100005],b[100005];

int main()
{
    int m,n;
    long long ans=0;//极端值容易存不下，所以要开long long
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+m+1);//为方便二分查找，要从小到大排序
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        a[0]=-2e6,a[m+1]=2e6;//将两个哨兵定好初始值
        int l=1-1,r=m+1;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(a[mid]<b[i])
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }
        ans+=min(abs(a[l]-b[i]),abs(a[r]-b[i]));//将这个学生不满意度的最小值加到所有学生不满意度的最小值中
    }
    cout<<ans;
    return 0;
}

注意：哨兵的存在是为了避免l=0或r=n+1这种情况(这种不成立)，这样就不会让l=0或r=n+1