NKSGAME – spoj

Đề bài:

• http://vn.spoj.com/problems/NKSGAME/

Thuật toán:

Bài yêu cầu với mỗi số [latex]b[i][/latex] tìm [latex]c[j][/latex] sao cho [latex]|b[i]+c[j]|[/latex] nhỏ nhất. Suy ra chọn sao cho [latex]b[i]+c[j][/latex] có giá trị gần [latex]0[/latex] nhất

Thuật toán sẽ là:

1. Sắp xếp lại mảng [latex]c[][/latex].
2. Với mỗi [latex]b[i][/latex] tìm kiếm nhị phân [latex]c[j][/latex] thỏa mãn [latex]b[i]+c[j][/latex] có giá trị gần [latex]0[/latex] nhất.

Nếu chưa hiểu rõ bạn có thể xem code bên dưới.

Code:

• xem code trên ideone

#include 

using namespace std;

const int maxn = 100009;
const int oo = 2000000009;
int i, j, n, ans, tmp, b[maxn], a[maxn];

bool cmp (int x, int y) {
     return(x < y);
}

int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    sort (b+1, b+n+1, cmp);
    ans = oo;
    for (i = 1; i <= n; i++) {
        tmp = lower_bound(b+1,b+n+1,0-a[i]) - b;
        if (tmp > n) tmp = n;
        ans = min(ans, abs(a[i] + b[tmp]));
        if (tmp == 1) continue;
        ans = min(ans, abs(a[i] + b[tmp-1]));
    }
    cout << ans;
    return 0;
}