二分查找

代码套路分析

常用代码

假定数组下标从0开始，到N-1结束

int l=-1,r=N; //l和r均在数组之外
while(l+1!=r)
{
    int mid = (l+r)/2; //将mid作为l和r的中间值，并向下取整
    if(check(mid))  //此处check函数也可以是其他判断语句，依据题目而定
        l=mid;
   	else
        r=mid;
}
return l;  //return r;也可以，根据题目来定

例题分析

烦恼的高考志愿

题干

烦恼的高考志愿
题目描述

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

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

输入格式

第一行读入两个整数 m,n。m 表示学校数，n 表示学生数。

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

输出格式

输出一行，为最小的不满度之和。

样例输入#1

4 3<br>
513 598 567 689<br>
500 600 550<br>
```<br>
样例输出 #1<br>
```<br>
32<br>
```<br>
提示<br>
数据范围：<br>
对于 30\% 的数据，1<= n,m<=1000，估分和录取线 <=10000；<br>
对于 100\% 的数据，1\<= n,m<=100000，估分和录取线 <=1000000 且均为正整数。<br>
    </details>

代码

#include <bits/stdc++.h>
using namespace std;
long long sum=0,m,n; //n 学生数，m 学校数 
int score[100005],line[100005];

int search(int sre)  //sre 每个学生的预估分数
{
	int l=0,r=m+1;  //l和r均在数组之外，l比数组最小下标还要小，r比最大下标还要大。
	while(l+1!=r)  //513 567 598 689
	{
		int mid = (l+r)/2;
		if(sre>line[mid])
			l=mid;
		else
			r=mid;
	}
	if(l==0)
		return abs(line[1]-sre);
	else return min(abs(line[r]-sre),abs(line[l]-sre)); 
}
int main()
{
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>line[i];
	
	sort(line+1,line+m+1); //把分数线做一个快排，方便使用二分查找
	
	for(int i=1;i<=n;i++)
		cin>>score[i];
	for(int i=1;i<=n;i++)
		sum+=search(score[i]);
	cout<<sum;
	return 0;
}