蒟蒻80分,找不出错,用的lower_bound,求助awa

P1678 烦恼的高考志愿

MC_BS_shy @ 2021-12-08 20:46:40

rt


#include<iostream>
#include<algorithm>
using namespace std;
int arr[1000000]={0};//数组 
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    sort(arr+1,arr+n+1);
    int s=0;
    for(int i=0;i<m;i++){
        int key;
        cin>>key;
        int id=lower_bound(arr+1,arr+1+n,key)-arr;
        if(id==n+1){
            s+=key-arr[n+1];
            continue;
        }
        if(id==1){
            s+=arr[1]-key;
            continue;
        }
        if(key-arr[id-1]<arr[id]-key){
                s+=key-arr[id-1];

        }else{
                s+=arr[id]-key; 
        }
    }
    cout<<s;
    return 0;
}

by LeslieWWWWW @ 2022-06-23 00:37:07

不出所料,你和我错的一样: id == n + 1的情况代表没有找到大于或等于key的数,那么应该是s += key - arr[n];(注意arr数组下标有效范围本来就只到n!)


|