[数据结构与算法]P1678 烦恼的高考志愿 二分和STL

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n,m,x,sum=0;
	cin>>n>>m;
	long long num[100001]={0};
	for(long long i=0;i<n;i++)cin>>num[i];
	sort(num,num+n);
	while(m--){
		cin>>x;
		long long flag=lower_bound(num,num+n,x)-num;
		if(flag==n)sum+=fabs(x-num[flag-1]);//特判
		else if(flag==0)sum+=fabs(num[flag]-x);//特判
		else {
			if(fabs(num[flag]-x)>fabs(num[flag-1]-x)){
				sum+=fabs(num[flag-1]-x);
			}
			else  sum+=fabs(num[flag]-x);
		}
	}
	cout<<sum<<endl;
	return 0;
} 

第一种用STL直接解

#include<bits/stdc++.h>
using namespace std;
int main(){
	int m,n;
	cin>>m>>n;
	int a[m+10],b[n+10];
	for(int i=0;i<m;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	sort(a,a+m);
	int sum=0,k=0;
	for(int i=0;i<n;i++){
		int left=0,right=m-1;
		while(left<right-1){
			int mid=(left+right)/2;
			if(a[mid]<=b[i])left=mid;
			else right=mid;
		}
		if(a[left]>=b[i])sum+=a[left]-b[i];//没有比它大的要特判 
		else sum+=min(fabs(a[right]-b[i]),fabs(a[right-1]-b[i])); 
	}
	cout<<sum;
	return 0;
}

手写二分