【洛谷】P1678 烦恼的高考志愿 （二分）

题目描述在这里：P1678

这道题用二分的思路就很容易想出，先把学校分数排好序，根据不满意度的定义，我们只需要每次找到第一个大于学生成绩的学校分数，然后再和最后一个小于学生分数的院校分数分别与学生成绩做差再打绝对值进行比较，取最小的一个累加到ans里就好啦

代码如下

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 100010
int m[maxn],n[maxn],M,N;  //分别定义学校分数，学生分数，学校个数，学生个数
long long ans = 0;  //ans要开long long 不然有一个数据点会WA
//y总的板子x
int find(int x) {
	int l=1,r=M,mid;
	while(l<r) {
		if(m[mid=l+r>>1]<=x)
		l=mid+1;
		else r=mid;
	}
	return l;
}
int main() {
	cin >>M>>N;
	for(int i=1;i<=M;i++) cin >>m[i];
	for(int i=1;i<=N;i++) cin >>n[i];
	sort(m+1,m+M+1); //排序
	
for (int i=1;i<=N;i++) {
    int k=find(n[i]);。 //防止在程序内多次调用函数，说到底这种题目也不需要写函数嘛。。。
    if(n[i]<=m[1])
    ans += m[1]-n[i];  //特判，否则只有七十分，因为如果返回的是第一个下标，那么m[k-1]就是m[0],m[0]没有初始化，不知道会出现啥东西xxx
    else。             //应该是这个原因？反正这样就AC了
	ans += min(abs(m[k]-n[i]),abs(m[k-1]-n[i]));
	}
	cout << ans;

	return 0;
}