# 14105: 【原4105】difference

### 题目描述

author: Lmxyy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4105

## Description

dhh有一个数据集，里面有$$N$$个整数$$A_1 \sim A_N$$。接下来他会得到$$M$$个数字$$B_1 \sim B_M$$，他需要很快地算出对于每个$$B_i$$，他与$$A$$数组中所有元素构成的差中最小的多少？或者更严谨，对于每个$$1 \le i \le M$$，

## Sample Input

5 4
2 3 1 2 12
16
2
9
14


## Sample Output

4
0
3
2


## FineArtz's solution

/* difference */
#include <iostream>
#include <cmath>
using namespace std;

struct Heap{
int heapsize = 0;
int a[200005] = {0};

void swap(int x, int y){
int t = a[x];
a[x] = a[y];
a[y] = t;
}

void siftup(int x){
while (x != 1){
if (a[x] < a[x >> 1]){
swap(x, x >> 1);
x >>= 1;
}
else
break;
}
}

void siftdown(){
int i = 2;
while (i <= heapsize){
if (i + 1 <= heapsize && a[i] > a[i + 1])
++i;
if (a[i >> 1] > a[i]){
swap(i, i >> 1);
i <<= 1;
}
else
break;
}
}

void insert(int x){
a[++heapsize] = x;
siftup(heapsize);
}

void pop(){
swap(1, heapsize);
--heapsize;
siftdown();
}

int top(){
return a[1];
}
};

int n, m;
Heap heap;
int a[200005];

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i){
int t;
cin >> t;
heap.insert(t);
}
for (int i = 1; i <= n; ++i){
a[i] = heap.top();
//cout << a[i] << endl;
heap.pop();
}

while (m--){
int q;
cin >> q;
int l = 1, r = n, mid;
while (l <= r){
mid = (l + r) / 2;
if (a[mid] == q)
break;
if (a[mid] > q)
r = mid - 1;
else
l = mid + 1;
}
int ans = abs(q - a[mid]);
if (mid > 1){
ans = min(ans, abs(q - a[mid - 1]));
}
if (mid < n){
ans = min(ans, abs(q - a[mid + 1]));
}
cout << ans << '\n';
}
return 0;
}


## WashSwang's solution

#include <iostream>
#include <algorithm>
using namespace std;
struct btype{
int v;
int ind;
} b[200001];
bool cmp(btype x,btype y){
return x.v<y.v;
}
int a[200001],m,n,l,r,mid,ans[200001],minn;
int main() {
scanf("%d%d",&n,&m);
for (int i=0;i<n;++i) scanf("%d",&a[i]);
sort(a,a+n);
for (int i=0;i<m;++i) {scanf("%d",&b[i].v);b[i].ind=i;}
sort(b,b+m,cmp);
l=0;
for (int i=0;i<m;++i){
r=n-1;
while (l<=r){
mid=(l+r)/2;
if (a[mid]<b[i].v) l=mid+1;
else if (a[mid]>b[i].v) r=mid-1;
else {
l=mid;
break;
}
}
minn=2000000001;
if (l<n) minn=min(minn,abs(a[l]-b[i].v));
if (l>=1) minn=min(minn,abs(a[l-1]-b[i].v));
ans[b[i].ind]=minn;
}
for (int i=0;i<m;++i)
printf("%d\n",ans[i]);
return 0;
}


## yyong119's solution

#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX_N 200010

int a[MAX_N];
int n, m;

int binary_search(int x) {

int l = 0, r = n - 1, mid;
int delta = 0x7fffffff;
while (l < r) {
mid = (l + r) >> 1;
if (x > a[mid])
l = mid + 1;
else if (x < a[mid])
r = mid - 1;
else
return 0;
}

for (int i = max(0, mid - 3); i < min(n, mid + 3); ++i)
delta = min(delta, abs(a[i] - x));
return delta;
}

int main() {

scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
sort(a, a + n);
while(m--) {
int x;
scanf("%d", &x);
int ans = binary_search(x);
printf("%d\n", ans);
}
return 0;
}