题目链接
暴力的时间复杂度是O(
n
2
n^2
n2)，只能在查询的时候优化一下，可以手写一个左闭右开的二分，也可以使用库函数
l
o
w
e
r
lower
lower_
b
o
u
n
d
bound
bound,时间复杂度变成
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
const int maxn = 2e5 + 7;
int a[maxn], x;
set<int> s;
int main()
{
int n, m;
scanf(" %d %d",&n,&m);
for(int i = 0; i < n; i++)
scanf(" %d",&a[i]);
sort(a,a+n);
int ansm = 0x3f3f3f3f, t;
for(int i = 0; i < m; i++)
{
scanf(" %d",&x);
int idx = lower_bound(a, a + n, x) - a;
for(int j = idx - 1; j <= idx; j++)
if(j < n && j >= 0) ansm = min(ansm,abs(x-a[j]));
}
printf("%d\n",ansm);
return 0;
}