P1678 烦恼的高考志愿——题解

解题思路

先把学校分数线排序。对于每个学生，用 lower_bound 找到第一个不小于估分的分数线；最近值只可能是该位置和它的前一个位置，比较二者差值即可。累加答案时使用 long long。

复杂度分析

排序 $O(m\log m)$，询问 $O(n\log m)$，空间复杂度 $O(m)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int m,n;cin>>m>>n;vector<int>a(m);for(int&i:a)cin>>i;sort(a.begin(),a.end());
    long long ans=0;
    while(n--){
        int x;cin>>x;auto it=lower_bound(a.begin(),a.end(),x);
        long long best=4e18;
        if(it!=a.end())best=min(best,(long long)*it-x);
        if(it!=a.begin()){--it;best=min(best,(long long)x-*it);}
        ans+=best;
    }
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int m,n;cin>>m>>n;vectora(m);for(int&i:a)cin>>i;sort(a.begin(),a.end()); long long ans=0; while(n--){ int x;cin>>x;auto it=lower_bound(a.begin(),a.end(),x); long long best=4e18; if(it!=a.end())best=min(best,(long long)*it-x); if(it!=a.begin()){--it;best=min(best,(long long)x-*it);} ans+=best; } cout<<ans<<'\n';return 0; }