14105: 【原4105】difference

题目描述

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

Description

众所周知，dhh是个数学master，他最近在研究一个问题。

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

formula

Input Format

第一行两个个正整数\(N,M\)。

第二行N个整数\(A_i\)。

再接下来\(M\)，每行一个正整数\(B_i\)。

Output Format

输出共\(M\)行，对于每个\(B_i\)，输出一行表示\(ans_i\)。

Sample Input

Sample Output

Data Range

对于\(60\%\)的数据，\(N,M \le 1000\)。

对于另外\(10\%\)的数据，数据完全随机。

对于另外\(10\%\)的数据，\( \vert A_i \vert, \vert B_i \vert \le 10^6 \)。

对于\(100\%\)的数据，\(N,M \le 2 \times 10^5\)，\( \vert A_i \vert, \vert B_i \vert \le 10^9 \)。

Hint

为保证你能正常AC此题，如果tle，请尝试使用scanf/printf或者读入/输出优化。

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;
}