Hướng dẫn giải của SpringBear và dãy số

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.


Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.

Tác giả: dinhwe2612

Sắp tăng dần hai dãy ~a~ và ~b~.

Với mỗi ~a_i~, ta cần tìm ~j~ sao cho ~|a_i+b_j|~ là nhỏ nhất.

Ta thấy khi ~i~ tăng thì ~a_i~ tăng nên ~b_j~ giảm và ~j~ sẽ giảm theo. Do đó có thể sử dụng hai con trỏ để duyệt trong ~O(n)~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;
const int oo = 2e9 + 100;

int n, a[N], b[N];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    int res = oo;
    for(int i = 1, j = n; i <= n; ++i) {
        while(j > 1 && abs(a[i] + b[j]) >= abs(a[i] + b[j - 1])) --j;
        res = min(res, abs(a[i] + b[j]));
    }
    cout << res;

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.