C++Tìm kiếm nhị phân - SGAME

Được viết bởi: Daniel


Đề bài

Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm $n$ số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: $b_1, b_2,..., b_n$ còn dãy số mà bạn thứ hai chọn là $c_1, c_2,..., c_n$.

Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng $b_i (1 <= i <= n)$, còn bạn thứ hai đưa ra số hạng $c_j (1 <= j <= n)$ thì giá của lượt chơi đó sẽ là $|b_i + c_j|$. Ví dụ: Giả sử dãy số bạn thứ nhất chọn là $1, -2$; còn dãy số mà bạn thứ hai chọn là $2, 3$. Khi đó các khả năng có thể của một lượt chơi là $(1, 2), (1, 3), (-2, 2), (-2, 3)$. Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là $0$ tương ứng với giá của lượt chơi $(-2, -2)$.

Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.

Dữ liệu vào:

  • Dòng đầu tiên chứa số nguyên dương $n (n <= 10^5)$
  • Dòng thứ hai chứa dãy số nguyên $b_1, b_2,.., b_n (|b_i| <= 10^9)$;
  • Dòng thứ ba chứa dãy số nguyên $c_1, c_2,..., c_n (|c_i| <= 10^9)$.

Dữ liệu ra:

  • Ghi ra giá nhỏ nhất tìm được.

Ví dụ:

//Input

2
1 -2
2 3
//Output
0

Nhận xét

  • Nếu ta xét tất cả các trường hợp, chạy hai vòng lặp lồng nhau như sau :
    define INF (long long)(1e13)
    long long result = INF;
    for (int i = 1; i<=n; i++)
        for (int j = 1; j<=n; j++)
            result = min(result, abs(b[i] + c[j]));
  • Theo cách code trên, giả sử trong trường hợp xấu nhất, $n = 10^5$ thì số lần lặp sẽ là $10^{10}$, quá lớn để có thể chạy trong 1s.
  • Ta nhận xét rằng nếu tìm được hai chỉ số $x$ và $y$, $(1 <= x, y <= n)$ sao cho $b[x]$ và $b[y]$ có giá trị "gần nhất" với $-c[i]$ thì kết quả của bài toán sẽ là $min(|b[x] + c[i]|, |b[y] + c[i]|)$, bởi giả sử $b[x] = - c[i] + k$ thì $|b[x] + c[i]| = |-c[i] + k + c[i]| = |k|$, như vậy ta cần làm cho giá trị của $|k|$ nhỏ nhất, tức là $b[x]$ phải mang giá trị sát với $c[i]$ nhất, chứng minh tương tự với trường hợp $b[y]$.

Chuẩn bị

  • Trước hết ta sắp xếp mảng b cho tiện xử lí:
    cin >> n;
    for (int i = 1; i<=n; i++)
        cin >> b[i];
    for (int i = 1; i<=n; i++)
        cin >> c[i];
    sort(b + 1, b + n + 1);

Xây dựng thuật toán

  • Sau khi sắp xếp mảng b, bài toán trở thành tìm $x$ sao cho $b[x] <= -c[i]$ và tìm $y$ sao cho $b[y] >= -c[i]$.
  • Ta sử dụng thuật toán tìm kiếm nhị phân:
    //Tìm chỉ số lớn nhất của phần tử mảng b thoả mãn điều kiện <= - c[i]
    int tknp1(int i)
    {
    int L = 1, R = n, mid, result = -1;
    while (L <= R) {
        mid = (L + R) >> 1;
        if (b[mid] < -c[i]) {
            result = mid;
            L = mid + 1;
        }
        else
            if (b[mid] == -c[i]) return mid;
        else
            R = mid - 1;
    }
    return result;
    }
    //Tìm chỉ số nhỏ nhất của phần tử mảng b thoả mãn điều kiện >= -c[i]
    int tknp2(int i) {
    int L = 1, R = n, mid, result = -1;
    while (L <= R) {
        mid = (L + R) >> 1;
        if (b[mid] > -c[i]) {
            result = mid;
            R = mid - 1;
        }
        else
            if (b[mid] == -c[i]) return mid;
        else
            L = mid + 1;
    }
    return result;
    }

    Giải thích:

  • Ở hàm $tknp1$, ta gọi khoảng nghiệm đang xét là $[L, R]$, trong đó $L = 1, R = n$, khoảng nghiệm này có thể chứa chỉ số mà ta cần tìm.
  • Ta sử dụng vòng lặp $while$ với điều kiện lặp là $L <= R$, điều kiện này là để tránh khỏi bị lặp vô hạn.
  • Gọi $mid = (L + R) >> 1 = (L + R)/2$, nếu $b[mid] thoả mãn điều kiện < -c[i]$, ta lưu lại $res = mid$, nhưng bởi ta cần nghiệm tối ưu, tức là cần chỉ số lớn hơn để cho $b[mid]$ có giá trị "gần" hơn giá trị của $-c[i]$ nên ta cho $L = mid + 1$, khi này khoảng nghiệm đang xét sẽ trở thành $[mid + 1, R]$ và ta tiếp tục lặp lại vòng lặp. Nếu $b[mid] = -c[i]$ thì ta có thể thấy $mid$ chính là nghiệm tối ưu cần tìm nên hàm trả về kết quả.
  • Nếu $b[i]$ không thuộc trường hợp nào trong hai trường hợp trên, tức là ($b[mid] > -c[i]$), khi này ta sẽ cho $L = mid + 1$, bởi với $mid + 1, mid + 2,... n$ thì $b[mid]$ đều sẽ lớn hơn $-c[i]$, ta không cần phải xét chúng làm gì cho tốn thêm chi phí.
  • Hàm $tknp2$ có tác dụng ngược lại với hàm $tknp1$, thay vì tìm chỉ số lớn nhất thì ta tìm chỉ số nhỏ nhất sao cho $b[mid] >= -c[i]$.

Full code

#include <bits/stdc++.h>
#define MAX int(1e5 + 6)
#define INF int(1e9 * 2 + 10)
using namespace std;
int n, c[MAX], b[MAX];
//tim phan tu cua b lon nhat tm dk <= - c[i]
int tknp1(int i)
{
    int L = 1, R = n, mid, result = -1;
    while (L <= R) {
        mid = (L + R) >> 1;
        if (b[mid] < -c[i]) {
            result = mid;
            L = mid + 1;
        }
        else
            if (b[mid] == -c[i]) return mid;
        else
            R = mid - 1;
    }
    return result;
}
//tim phan tu cua b nho nhat tm dc >= -c[i]
int tknp2(int i) {
    int L = 1, R = n, mid, result = -1;
    while (L <= R) {
        mid = (L + R) >> 1;
        if (b[mid] > -c[i]) {
            result = mid;
            R = mid - 1;
        }
        else
            if (b[mid] == -c[i]) return mid;
        else
            L = mid + 1;
    }
    return result;
}
int main()
{
    freopen("SEQGAME.INP", "r", stdin);
    freopen("SEQGAME.OUT", "w", stdout);
    cin >> n;
    for (int i = 1; i<=n; i++)
        cin >> b[i];
    for (int i = 1; i<=n; i++)
        cin >> c[i];
    int result = INF;
    sort(b + 1, b + n + 1);
    for (int i = 1; i<=n; i++)
    {
        if (tknp1(i) != -1)
            result = min(result, abs(c[i] + b[tknp1(i)]));
        if (tknp2(i) != -1)
            result = min(result, abs(c[i] + b[tknp2(i)]));
    }
    cout << result;
    return 0;
}

Nguồn bài tập: Here

Link bài tập

Thiết kế thuật giải: Bấm vào đây

Posted on June 24, 2021 10:13:55 PM


3
Donate free




Đăng nhập để tham gia thảo luận! Hoặc bạn có thể bình luận bằng facebook ở dưới.