7 solutions
Information
- ID
- 280
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 279
- Accepted
- 53
- Uploaded By
这个题就只需要查找大于等于该数的第一个数和小于等于该数的第一个数,来比较目标数与上述两个数的差值,选择差值较小的那个即可
#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;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.