Hướng dẫn cho Tìm cặp số

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

Tóm tắt đề bài

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử đã được sắp xếp tăng dần và một số nguyên \(X\). Hãy tìm hai vị trí \(i\) và \(j\) (\(i \neq j\)) sao cho \(A_i + A_j = X\). Nếu có nhiều cặp, chỉ cần in ra một cặp bất kỳ. Nếu không có cặp nào thỏa mãn, in ra "No solution".

Phân tích

Điều kiện: \(2 \leq n \leq 10^6\), \(0 \leq A_i, X \leq 10^9\).
Đặc điểm quan trọng: Dãy số đã được sắp xếp tăng dần. Đây là chìa khóa để tối ưu hóa việc tìm kiếm thay vì duyệt qua mọi cặp số.
Giới hạn thời gian: Với \(n = 10^6\), thuật toán có độ phức tạp \(O(n^2)\) chắc chắn sẽ bị quá thời gian (TLE). Chúng ta cần thuật toán có độ phức tạp khoảng \(O(n \log n)\) hoặc \(O(n)\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Sử dụng hai vòng lặp lồng nhau để duyệt qua tất cả các cặp \((i, j)\) có thể có và kiểm tra xem tổng của chúng có bằng \(X\) hay không.

Độ phức tạp

Thời gian: \(O(n^2)\)
Đánh giá: Chỉ phù hợp với \(n \leq 5000\). Với \(n = 10^6\), số phép tính có thể lên tới \(10^{12}\), vượt quá giới hạn 1 giây.

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] + a[j] == x) {
                cout << i + 1 << " " << j + 1 << endl;
                return 0;
            }
        }
    }
    cout << "No solution" << endl;
    return 0;
}

Python

n, x = map(int, input().split())
a = list(map(int, input().split()))

found = False
for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == x:
            print(i + 1, j + 1)
            found = True
            break
    if found:
        break
if not found:
    print("No solution")

Hướng giải quyết (Tối ưu)

Vì mảng đã được sắp xếp, ta có thể sử dụng phương pháp Tìm kiếm nhị phân (Binary Search) hoặc Kỹ thuật hai con trỏ (Two Pointers). Dưới đây là phân tích cách dùng Tìm kiếm nhị phân (giống với code mẫu):

Thuật toán Tìm kiếm nhị phân

Duyệt qua từng phần tử \(A_i\) trong mảng (với \(i\) từ \(0\) đến \(n-2\)).
Với mỗi \(A_i\), ta cần tìm một phần tử \(A_j\) sao cho \(A_j = X - A_i\).
Vì mảng đã sắp xếp, ta có thể tìm kiếm giá trị \(target = X - A_i\) trong đoạn từ \([i+1, n-1]\) bằng tìm kiếm nhị phân.
Nếu tìm thấy \(j\), in ra \(i+1\) và \(j+1\) rồi kết thúc chương trình.
Nếu duyệt hết mảng mà không tìm thấy, in "No solution".

Tại sao cách này hiệu quả?

Thay vì phải duyệt qua \(n\) phần tử để tìm \(A_j\), tìm kiếm nhị phân chỉ mất \(\log n\) bước.
Tổng thời gian sẽ là \(n \times \log n\), hoàn toàn đáp ứng được giới hạn thời gian với \(n = 10^6\).

Độ phức tạp

Thời gian: \(O(n \log n)\)
Bộ nhớ: \(O(n)\) để lưu trữ mảng.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

// Hàm tìm kiếm nhị phân trả về chỉ số của giá trị cần tìm
int binarySearch(const vector<long long>& a, int left, int right, long long target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

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

    int n;
    long long x;
    cin >> n >> x;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        long long target = x - a[i];
        // Tìm target trong đoạn còn lại của mảng
        int j = binarySearch(a, i + 1, n - 1, target);
        if (j != -1) {
            cout << i + 1 << " " << j + 1 << endl;
            return 0;
        }
    }

    cout << "No solution" << endl;
    return 0;
}

Python

import sys

def binSearch(a, x, l, r):
    while l <= r:
        m = (l + r) // 2
        if a[m] == x:
            return m
        if a[m] < x:
            l = m + 1
        else:
            r = m - 1
    return -1

def solve():
    # Đọc dữ liệu nhanh
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    x = int(input_data[1])
    a = list(map(int, input_data[2:]))

    for i in range(n):
        target = x - a[i]
        # Tìm target trong đoạn từ i+1 đến cuối mảng
        j = binSearch(a, target, i + 1, n - 1)
        if j != -1:
            print(i + 1, j + 1)
            return

    print("No solution")

if __name__ == "__main__":
    solve()

Bình luận (1)

Tải bình luận...