P1678 烦恼的高考志愿 二分查找的板子题

二分查找的一道题目#

题解：

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int> school,point;
void solve(){ll res=0;int m,n;cin>>m>>n;for(int i=0;i<m;i++){int x;cin>>x;school.push_back(x);}for(int i=0;i<n;i++){int x;cin>>x;point.push_back(x);}sort(school.begin(),school.end());for(int i=0;i<n;i++){int idx = lower_bound(school.begin(),school.end(),point[i]) - school.begin();if(idx==0){res += abs(school[0]-point[i]);}else if(idx==m){res += abs(school[m-1]-point[i]);}else{res += min(abs(school[idx]-point[i]),abs(school[idx-1]-point[i]));}}cout << res << '\n';
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);solve();
}

注意：

1. 最后的res开long long 因为累加起来会很大
2. 关于 lower_bound
   lower_bound 返回的是第一个不小于目标值的插入位置
   类似于 植树问题 在一个有5个元素（树木）的数组中，植入一棵树（6个空隙都可以植树）