P1678 烦恼的高考志愿

我会带着你远行 2022-11-11 13:11 148阅读 0赞

[  
传送][Link 1]

找到位置，别忘记做差的绝对值，前后比较得出最小的期望值。

//#include<bits/stdc++.h>
    #include <stdio.h>
    #include <iostream>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    #include<vector>
    #include<queue>
    #define ll long long
    #define ios ios::sync_with_stdio(false);cin.tie(0)
    #define rep(i,a,b) for(int i=a;i<=b;++i)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    #define scf(x) scanf("%lld",&x)
    #define prf(x) printf("%lld\n",x)
    #define deprf(x) printf("[%lld]\n",x)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define inf 2147483647
    const int mod=1e9+7;
    const int maxn=1e5+7;
    using namespace std;
    int maxnn = 1e8;
    
    int read(){ //快读
        int x=0,f=1;
        char c=getchar();
        while(c<'0'||c>'9'){ 
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){ 
            x=x*10+c-'0';
            c=getchar();
        }
        return x*f;
    }
    
    
    void sovle()
    { 
    
    }
    int a[maxn];
    int main()
    { 
        ios;
        int m = read(),n = read();
        rep(i,1,m){ 
            a[i] = read();
        }
        sort(a+1,a+1+m);
        long sum = 0;
        a[0] = maxnn;
        a[m+1] = maxnn;
        while(n--){ 
            int temp = read();
            int pos = lower_bound(a+1,a+1+m,temp)-a;
            //cout << pos << endl;
            int ans = min(min(abs(temp-a[pos-1]), abs(temp-a[pos+1])),abs(temp-a[pos]));
            //cout << ans << endl;
            sum += ans;
        }
        cout << sum;
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1678