[Lập trình newbie] Mỗi ngày một bài toán (số 13)

[11520132]

Thuật em nlogn đấy ạ :sogood:

anh chưa test cái pascal của em, mà em cho nó random in ra 2 dòng 100k số thử.
nếu không tính thời gian tạo với in số, chỉ xử lí không thì thuật toán tệ nhất cũng không quá 1s.

[quoctinvn]

chạy vô tư ạ :smile:

anh chưa test cái pascal của em, mà em cho nó random in ra 2 dòng 100k số thử.
nếu không tính thời gian tạo với in số, chỉ xử lí không thì thuật toán tệ nhất cũng không quá 1s.

[quoctinvn]

Code C++ :salute::salute:

#include <stdio.h>
using namespace std;
int n;
int a[100000]; int b[100000];
void init()
{
    int i;
    scanf("%d",&n);
    for (i=0;i <= n-1;i++)
        scanf("%d",&a[i]);
    for (i=0;i <= n-1;i++)
        scanf("%d",&b[i]);
}
void QuickSort(int l, int h)
{
    if (l >= h) return;
    int i = l; int j = h;
    int temp;
    int x = b[(l+h)/2];
    do
    {
        while (b[i] > x) i++;
        while (b[j] < x) j--;
        if (i <= j)
        {
            if (i<j)
            {
                temp = b[i];
                b[i] = b[j];
                b[j] = temp;
            }
            i++; j--;
        }
    } while (i<=j);
    QuickSort(l,j); QuickSort(i,h);
}
int abs(int x)
{
    if (x >= 0) return(x);
    return(-x);
}
int BinarySearch(int s)
{
    int mid,l,r;
    l = 0; r = n-1;
    while (l < r-1)
    {
        mid = (l+r)/2;
        if (b[mid]==s) return(mid);
        if (b[mid]>s)
        {
            l = mid;
        }
        if (b[mid]<s)
        {
            r = mid;
        }
    }
    return l;
}

int main()
{
    init();
    QuickSort(0,n-1);
    int minv,i,k;
    minv=2000000000;
    for (i=0;i<=n-1;i++)
    {
        k = BinarySearch(-a[i]);
        if (abs(a[i]+b[k])==0)
        {
            minv = 0;
            break;
        }
        if (minv > abs(a[i]+b[k])) minv = abs(a[i]+b[k]);
        if ((k+1 <= n-1) && (minv > abs(a[i]+b[k+1]))) minv = abs(a[i]+b[k+1]);
    }
    printf("%d\n",minv);
    return 0;
}

[quoctinvn]

ep 14 chưa ạ