50分求助

soyouwilllikethem111 @ 2023-12-26 12:40:10

#include<bits/stdc++.h>
using namespace std;
long long  a[99999999],b[99999999]; 
int main()
{
    long long n,x=0,m,min=99999999;//定义变量，数组
    cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }//输入a，b数组 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(abs(b[i]-a[j])<min)
            {
                min=abs(b[i]-a[j]);
            }
        } 
        x=x+min;
        min=99999999;
    }//计算最小不满值 
    cout<<x;
    return 0;
}

by soyouwilllikethem111 @ 2023-12-26 12:41:31

救命

by soyouwilllikethem111 @ 2023-12-26 12:45:01

测试点5，6，7，9，11过不了

by QWQ_HY_DFX @ 2023-12-26 13:23:29

题目说了，n,m \le 10^5，你这暴力做法O(nm)，会超时\ 这题得用二分

by soyouwilllikethem111 @ 2023-12-27 12:33:33

@hongyi328 我不会呀emmm......

by bean_daddy @ 2023-12-30 11:09:41

二分法 分为整数二分和小数二分，其实，你去看看 小数二分和整数二分每一个都有两个性质， 这两个性质 搞明白了，有模板的。最主要是写check的函数，这里的check 就是找到一个学校的分数小于等于学生的分数，此时需要考虑因为分差有正负，所以需要看看该点后面那个学校分数差值的绝对值是否更小，每次取这两个值的最小值即可。

by masonxiong @ 2024-02-07 16:58:18

@soyouwilllikethem111

不会二分的话，我认为贪心的解法会更加浅显易懂且复杂度优秀，可以做到O(nlogn+mlogm)且该解法和你的思路类似