思路

也就一个找大于等于该数的第一位数和小于等于该数的第一个数然后求最小值问题

#include<bits/stdc++.h>
using namespace std;
int m,n;
int num;
int a[10000000];
int find(int x){
	int l=0;
	int r=m-1;
	while(l<=r){
		int mid=l+r>>1;
		if(a[mid]>=x) r=mid-1;
		else l=mid+1;
	}
	if(num<=a[0]) return 1;//注意这一步 这道题数据不充分，不要这一步也能过，但下面有一道题是需要这一步的 
	return l;
}
int main(){
	cin>>m>>n;
	for(int i=0;i<m;i++){
		cin>>a[i];
	}
	sort(a,a+m);
	int sum=0;
	for(int i=0;i<n;i++){
		cin>>num;
		sum+=min(abs(num-a[find(num)]),abs(num-a[find(num)-1]));
	}
	cout<<sum;
	return 0;
} 

二分,找最接近他的数字

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
ll m, n, ans;
ll a[N], b[N];
ll Next(ll l) {
	ll x = a[l];
	for (ll i = l + 1; i <= m; ++i) {
		if (a[i] != x)return  a[i];
	}
	return x;
}
ll lbreach(ll x) {
	ll l = 0, r = m, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (a[mid] >= x)r = mid;
		else l = mid + 1;//就是本坐标
	}
	if (a[l] == x) return 0;
	if (l == 1) return a[1] - x;
	ll Numnext = Next(l - 1);
	return min(abs(Numnext - x), abs(a[l - 1] - x));
}
int main() {
	scanf("%lld%lld", &m, &n);
	for (ll i = 1; i <= m; ++i)scanf("%lld", &a[i]);
	for (ll i = 1; i <= n; ++i)scanf("%lld", &b[i]);
	sort(a + 1, a + 1 + m);
	for (ll i = 1; i <= n; ++i) {
		ans += lbreach(b[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

这个题就只需要查找大于等于该数的第一个数和小于等于该数的第一个数，来比较目标数与上述两个数的差值，选择差值较小的那个即可

#include<bits/stdc++.h>
using namespace std;
int a[100100]={0};
int b[100100]={0};
int m,n,i;

int zuoerfen(int x) //左二分查找
{
	int left=-1,right=m,mid;
	while (left+1<right)
	{
		mid=(left+right)/2;
		if (x<=a[mid])
		{
			right=mid;
		}
		else
		{
			left=mid;
		}
	}
	return right;
} 

int youerfen(int x) //右二分查找
{
	int left=-1,right=m,mid;

	while (left+1<right)
	{
		mid=(left+right)/2;
		if (x<a[mid])
		{
			right=mid;
		}
		else
		{
			left=mid;
		}

	}
	return left;
}

int main()
{
	scanf("%d %d",&m,&n);
	for (i=0;i<m;i++)
	{
		cin>>a[i];
	}
	for (i=0;i<n;i++)
	{
		cin>>b[i];
	}
	sort(a,a+m);
	long long sum=0; 
	for (i=0;i<n;i++)
	{
		int ansL=zuoerfen(b[i]);
		int ansR=youerfen(b[i]);
		if (ansL<0)
		{
			ansL=0;
		}
		if (ansL>=m)
		{
			ansL=m-1;
		}
		if (ansR<0)
		{
			ansR=0;
		}
		if (ansR>=m)
		{
			ansR=m-1;
		}//比较大小
		sum+=min(abs(b[i]-a[ansL]),abs(b[i]-a[ansR]));
	}
	cout<<sum<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int m,n;
	cin>>m>>n;
	int school[m+1];
	int student[n+1];
	for(int i=0;i<m;i++)cin>>school[i];
	for(int i=0;i<n;i++)cin>>student[i];
	sort(school,school+m);
	int res=0;
	for(int i=0;i<n;i++)
	{
		int a=abs(student[i]-*lower_bound(school,school+m,student[i]));
		int b=abs(student[i]-*(lower_bound(school,school+m,student[i])-1));
		res+=min(a,b);
	}
	cout<<res;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
#define LL long long
typedef pair<int,int> PII;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
const int N = 1e6 + 10, MOD = 1e9 + 10;
int a[N], b[N];
int n, m, res;

int ef1(int x)
{
    int l = 1, r = n;
    while( r > l )
    {
        int mid = l + r >> 1;
        if( a[mid] >= x )    r = mid;
        else    l = mid + 1;
    }
    return a[l];
}

int ef2(int x )
{
    int l = 1, r = n;
    while( r > l )
    {
        int mid = l + r + 1 >> 1;
        if( a[mid] <= x )   l = mid;
        else    r = mid - 1;
    }
    return a[l];
}
void solve()
{
    
    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+1+n);
    a[0] = -1, a[m+1] = 1e9;
    for(int i = 1; i <= m; i ++ )
        res += min(abs(b[i]-ef1(b[i])), abs(b[i]-ef2(b[i])));
    cout << res;
}
signed main()
{
    solve();
    return 0;
}

水题 对于这个题目 我们可以发现的是 我们如果数组排序好后 从第一个地方往后面查找的话 差值越来越大 贪心的思想 只要差值没有减小的话 就没有继续下去的必要 看似n*n的复杂度 其实更接近nlogn 代码 #include #include <math.h> #include using namespace std; const int N=10010; int res[N]; int finmin(int t,int num[],int n) { int min=9999; for(int i=0;i<n;++i) { if(abs(num[i]-t)<=min) min=abs(num[i]-t); else break; } return min; } int main() { int n,c,ans=0; cin>>n>>c; for(int i=0;i<n;++i) { cin>>res[i]; } sort(res,res+n); while(c--) { int t; cin>>t;

	ans+=finmin(t,res,n);
	
}
cout<<ans;

return 0;

}

原题链接

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100100],b[100100];
int find(int n,int m)
{
	int ans=0;
	for(int i=0;i<m;i++)
	{
		int l=0,r=n-1;
	    while(l<r)
	    {
		    int mid=l+r>>1;
		    if(a[mid]<=b[i]) l=mid+1;
		    else r=mid;
	    }
	    if(b[i]<=a[0])
	    {
	    	ans+=a[0]-b[i];
		}
		else
		{
			ans+=min(abs(a[l-1]-b[i]),abs(a[l]-b[i]));
		}
	}
	printf("%d",ans);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=0;i<m;i++)
	{
		scanf("%d",&b[i]);
	}
	sort(a,a+n);
	find(n,m);
	return 0;
}