急急急 为啥2分不对就20分啊 急急急

telankesi @ 2022-12-24 17:24:00

#include <stdio.h>
#include <math.h>
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    int a[100010];
    int b[100010];
    for (int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <=m-1 ; i++) {
        for (int j = i + 1; j <= m; j++) {
            if (a[j] < a[i]) {
                int k = a[i];
                a[i] = a[j];
                a[j] = k;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }

    long long sum = 0;

    for (int i = 0; i < n; i++) {
        int l = 0, r = n - 1, t;
        while (l<=r) {
            t = (l + r) / 2;
            if (a[t] >= b[i])r = t - 1;
            else l = t + 1;
        }
        int x = abs(a[l] - b[i]);
        int y = abs(a[r] - b[i]);
        sum +=  x < y ? x : y;

    }
    printf("%lld", sum);
    return 0;

}

by _maojun__ @ 2022-12-24 17:52:37

@telankesi n\le10^5 还用选排不然呢

by _maojun__ @ 2022-12-24 17:53:04

没有 T 掉应该是数组开到局部没有被允许开那么大

by _maojun__ @ 2022-12-24 17:59:49

@telankesi 目前来看应该是这四个问题：

#include <stdio.h>
#include <math.h>
#include<algorithm>
//test 
int a[100010];// 1.数组开到全局 
int b[100010];
int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &a[i]);
    }
    std::sort(a+1,a+m+1);   // 2.你用其他nlogn的排序也行，用个选排干什么 
    for (int i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }

    long long sum = 0;

    for (int i = 0; i < n; i++) {
        if(b[i]<=a[1]){ sum+=a[1]-b[i];continue; } //4.神奇的特判，见题解区 
        int l =1, r =m, t;  // 3.边界条件错了 
        while (l<=r) {
            t = (l + r) / 2;
            if (a[t] >= b[i])r = t - 1;
            else l = t + 1;
        }
        int x = abs(a[l] - b[i]);
        int y = abs(a[r] - b[i]);
        sum +=  x < y ? x : y;

    }
    printf("%lld", sum);
    return 0;

}

by telankesi @ 2022-12-24 18:08:48

@_maojun__ 谢谢哥哥

by telankesi @ 2022-12-24 18:14:42

@telankesi 为什么不能用选排??

by yszkddzyh @ 2023-01-05 20:04:23

@telankesi 复杂度太高，满足不了数据范围需要，选牌时间复杂度为 O(n^2)，本题 1\le m\le100000，而 100000^2=10000000000，一秒出不了结果，sort则是 O(n\log n) 的，因此要用sort