差值具有单峰特性,二分找最小值,为啥全错。。。

P1678 烦恼的高考志愿

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,同时维护最小不满意度,没必要上三个值判断


|