题解 P1678 【烦恼的高考志愿】

06ray · 2018-03-07 18:15:04 · 题解

这道题我AC的算法是二分（许多大佬用优先队列然而蒟蒻不会。。。）。

这道题如果使用二分思路会很简单。首先，将每个学校的录取分数线从大到小排序。接着开始二分查找，查找什么呢？我们应该查找每个学校录取分数线中最后一个小于等于每个同学分数的数，可以用一个while循环来模拟二分查找。

二分查找部分的思路如下所示：

首先定义两个变量，为l,r，分别为查找范围的左边界和右边界。接着while循环，首先判断while循环的条件是l<r,接着在循环里定义一个叫mid的变量，mid=(l+r)/2;然后判断：如果a[mid]，即录取分数线数组中的第mid个元素小于或等于那位同学的分数，mid+1赋值给l，否则，mid赋值给r。

最后查找完后，那么求录取分数线数组中的第l-1个元素和录取分数线数组中的第l个元素他们两与那位同学的估分的绝对值，那么答案就累加两个绝对值中最小的。

最后输出解即可。

复杂度为O(m*log(n));

下面献上代码(c++)

#include <iostream>
#include <cmath>
#include <algorithm>//头文件
using namespace std;//名字空间
int a[100100],b[100100];//定义两个数组，分别储存每个学校的分数线，和每个同学的估分
int main()//主函数
{
    int n,m;//定义n,m
    cin>>n>>m;//输入
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];//输入
    }
    for(int i=1; i<=m; i++)
    {
        cin>>b[i];//还是输入
    }
    sort(a+1,a+n+1);//把每个学校的分数线从小到大排序
    int ans=0;//答案一开始为0，因为要累加和。
    for(int i=1; i<=m; i++)
    {
        int l=0,r=n+1;//定义左边界与右边界
        while(l<r)
        {
            int mid=(l+r)/2;//取查找范围的中间值
            if(a[mid]<=b[i])//如果录取分数线数组中的第mid个元素小于或等于那位同学的分数
            {
                l=mid+1;//左边界就往右移
            }
            else
            {
                r=mid;//右边界就往左移
            }
        }
        if(b[i]<=a[1])//这里需要特判断一下，不然只能得70分
        {
            ans+=a[1]-b[i];
        }
        else
        {
            ans+=min(abs(a[l-1]-b[i]),abs(a[l]-b[i]));//加上两个绝对值中最小
        }
    }
    cout<<ans;//输出ans
    return 0;//结束程序
}