求时间复杂度

P1678 烦恼的高考志愿

11514zbs @ 2024-08-05 15:13:23

#include <cstdio>
#include <algorithm>

using namespace std;

long long a[1000005], b[1000005], n, m, j = 0, mi, x;

int main()
{
    scanf("%lld %lld", &n, &m);
    for (long long i = 0; i < n; i++)
    {
        scanf("%lld", &a[i]);
    }
    for (long long i = 0; i < m; i++)
    {
        scanf("%lld", &b[i]);
    }
    sort(a, a + n);
    sort(b, b + m);
    for (long long i = 0; i < m; i++)
    {
        for (; a[j] < b[i] && j < n; j++){}
        if (j == 0)
        {
            mi += abs(a[j] - b[i]);
        }
        else if (abs(a[j] - b[i]) < b[i] - a[j - 1])
        {
            mi += abs(a[j] - b[i]);
        }
        else
        {
            mi += b[i] - a[j - 1];
        }
    }
    printf("%lld\n", mi);
    return 0;
}

为什么我的比二分快近 100ms ,题解区都没有(?如有轻喷)跟我类似的代码?


by weak_in_code @ 2024-08-05 15:15:40


by 11514zbs @ 2024-08-05 15:15:59

貌似是 O(n \log n + m \log m + m + n) \approx O(n \log n + m \log n)


by 11514zbs @ 2024-08-05 15:16:32

@weak_in_code 不还有俩排序么?


by weak_in_code @ 2024-08-05 15:16:43

@11514zbs 下面循环是 O(n+m) 的,加上排序多个 \log


by TeraniRetZiger @ 2024-08-05 15:17:30

@11514zbs 双指针比二分牛太多。


by 11514zbs @ 2024-08-05 15:17:30

@weak_in_code thx

Orz


by 11514zbs @ 2024-08-05 15:19:16

@TeraniRetZiger

我乱写了一个双指针???好吧(我在刷二分来着


by kuuuun @ 2024-08-05 15:32:49

系统自带的sort一直都是很快的\ 虽然和二分一样都是 O(nlogn) \ 但系统带的常数比较小,n足够大的时候一般会比手打的快将近20ms


|