Đề 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