https://www.luogu.com.cn/problem/P1678
方法一:手写二分
#include<bits/stdc++.h>
using namespace std;
int m, n, a[100005], b;
long long ans;
int bs(int p){//二分查找 返回>=p的下标
int l=0, r=m-1;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(a[mid]>=p){
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
return ans;
}
int min_ab(int x){
int k=bs(x); //二分查找 返回>=p的下标
if(k==-1)k=m-1; //如果返回为-1说明数列中所有数都小于要查的数,那么结果应为数组最大下标
int kk=k-1==-1?0:(k-1); //求之前的下标,避免数组越界
if(a[k]==x)return 0; //如果相等返回0
else return min(abs(a[kk]-x),abs(a[k]-x)); //如果不相等返回相差小的那个值
}
int main()
{
cin>>m>>n;
for(int i=0; i<m; i++){
cin>>a[i];
}
sort(a, a+m);
for(int i=0; i<n; i++){
cin>>b;
ans+=min_ab(b);
}
cout<<ans;
return 0;
}
方法二:STL
#include<bits/stdc++.h> using namespace std; int m, n, a[100005], b; long long ans; int min_ab(int x){ //求最小值为不满意度 int lb=lower_bound(a,a+m,x)-a; //求大于等于x的第一个数的下标 int t=lb-1==-1?0:(lb-1); //求之前的下标,避免数组越界 if(a[lb]==x)return 0; //如果相等返回0 else return min(abs(a[lb]-x), abs(a[t]-x)); //如果不相等返回相差小的那个值 } int main() { cin>>m>>n; for(int i=0; i<m; i++){ cin>>a[i]; } sort(a, a+m); for(int i=0; i<n; i++){ cin>>b; ans+=min_ab(b); } cout<<ans; return 0; }