NKSGAME – spoj

Đề bài:

Thuật toán:

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

Thuật toán sẽ là:

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

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

Code:

#include <bits/stdc++.h>
 
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;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*