abch11 @ 2023-06-21 16:45:42
学校分数线排序后,每个人的分数与分数数组做差后的绝对值数组应该是下凹曲线吧,我想就是二分寻找差值取绝对值后的最小值,为啥爆红,有没有大佬分析一下,找找错误呀。。
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int m,n;
long long ans=0;
int a[1000000],b[1000000];
int main(){
cin>> m>> n;
a[0]=a[m+1]=-1000000;//设置边界,
//边界处具有最大差值,以满足单峰特性
for(int i=1;i<=m;i++)cin>> a[i];//学校
for(int i=0;i<n;i++)cin>> b[i];//学生
sort(a+1,a+m+1);//对学校分数线排序
//差值具有单峰特性
for(int i=0;i<n;i++){
int low=1,high=m,mid;
while(low<=high){
mid=low+(high-low)/2;
int fr,re,cu;
cu=abs(a[mid]-b[i]);fr=abs(a[mid-1]-b[i]);
re=abs(a[mid+1]-b[i]);//边界
if(cu<=fr&&cu<=re){//最小值处
ans+=cu;
break;
}
else if(cu>fr&&cu<re){//当前值在右边
high=mid-1;
}
else low=mid+1;//当前值在左边
}
}
cout<<ans;
return 0;
}
by LiJoQiao @ 2023-06-21 17:13:32
有没有考虑过a[mid-1]<a[mid]<b[i]<a[mid+1]
且cu<re
的情况
by LiJoQiao @ 2023-06-21 17:15:23
你想的太复杂了
二分查找时如果a[mid]
小于b[i]
就让low=mid+1
,大于则high=mid-1
,同时维护最小不满意度,没必要上三个值判断