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;
}
为什么我的比二分快近
by weak_in_code @ 2024-08-05 15:15:40
by 11514zbs @ 2024-08-05 15:15:59
貌似是
by 11514zbs @ 2024-08-05 15:16:32
@weak_in_code 不还有俩排序么?
by weak_in_code @ 2024-08-05 15:16:43
@11514zbs 下面循环是
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