Đề bài

Ở Hải Phòng không ai là không biết đến giáo sư NTH giấu tên. Ngoài đam mê đào tạo nhân tài tin học cấp quốc tế, giáo sư còn sở hữu vườn hoa siêu to khổng lồ với vô số các loài hoa: Phượng, Bạch Dương, Lan, Huệ, Thùy Dương,...

Ngày $20$ tháng $10$ sắp đến, giáo sư NTH muốn thu hoạch hoa để mang ra chợ bán. Vườn hoa của giáo sư gồm $10^{10}$ khóm hoa xếp thành hàng thẳng. Các khóm hoa được đánh số từ $1$ tới $10^{10}$ theo thứ tự từ trái qua phải.

Giáo sư giao cho Khánh tóc dài thực hiện nhiệm vụ này. Khánh tóc dài đặt mua $n$ chiếc máy cắt hoa siêu tốc. Lúc giao hàng, $n$ chiếc máy được đặt ở các khóm hoa $a_1,a_2,...,a_n$. Mỗi chiếc máy có thể thu hoạch hết số hoa ở khóm hoa mà nó đang đứng trong thời gian không đáng kể. Nhưng trong $1$ giây, nó chỉ di chuyển được sang một trong hai khóm hoa bên cạnh. Trong quá trình di chuyển, các máy có thể đi vào cùng một khóm hoa, hoặc một máy có thể "vượt" qua máy khác.

Giáo sư muốn Khánh thu hoạch $m$ khóm hoa ở các vị trí $b_1, b_2,..., b_m$ — những khóm hoa tươi và đẹp nhất. Khánh thắc mắc thời gian tối thiểu Khánh cần để thu hoạch toàn bộ số hoa này.

Input

Input gồm nhiều bộ test, mỗi bộ test được mô tả trong $4$ dòng:

• Dòng thứ nhất chứa hai số nguyên $n$ và $m$ $(1≤n,m≤10^5)$ — số máy cắt hoa và số khóm hoa cần thu hoạch.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $a_1, a_2,..., a_n (1 ≤ a_i ≤ 10^{10})$ — vị trí ban đầu của các máy.
• Dòng thứ ba chứa $m$ số nguyên phân biệt $b_1, b_2,..., b_m (1 ≤ b_j ≤ 10^{10})$ — vị trí của các khóm hoa cần thu hoạch.
• Dòng thứ tư là một dòng trống.

Input kết thúc bởi một dòng chứa hai số $0$ và bạn không phải xử lý dòng này. Tổng $n$ trong tất cả các test của một file input không quá $7.10^5$, tổng $m$ trong tất cả các test của một file input không quá $7.10^5$.

Output

Với mỗi bộ test, in ra một số nguyên duy nhất là số giây tối thiểu Khánh cần để thu hoạch hết các khóm hoa.

//Input
3 4
2 5 6
1 3 6 8

3 3
1 2 3
1 2 3

1 2
165
142 200

1 1
2207
1997

0 0

//Output
2 0 81 210

Note

Trong ví dụ thứ nhất:

• Máy thứ nhất cần $1$s để di chuyển từ khóm hoa $2$ sang khóm hoa $1$ và thu hoạch khóm hoa $1$.
• Máy thứ hai cần $2$s để di chuyển từ khóm hoa $5$ sang khóm hoa $3$ và thu hoạch khóm hoa $3$.
• Máy thứ ba cần $2$s để thu hoạch khóm hoa $6$ (thời gian thu hoạch rất nhỏ), di chuyển sang khóm hoa $8$ và thu hoạch khóm hoa $8$.

Nhận xét

• Ta nhận thấy nếu các máy có thể thu thập tất cả các khóm hoa trong khoảng thời gian $t$ thì tương tự với khoảng thời gian $t + 1, t + 2,...$ cũng vậy. Vì thế ta sử dụng kĩ thuật chia nhị phân.

Chuẩn bị

• Trước hết ta sắp xếp vị trí của các máy và vị trí của các khóm hoa theo thứ tự tăng dần cho tiện xử lí.

    while (cin >> n >> m) { //Liên tục đọc hai số, truyền vào biến n và m

        if (n == 0 && m == 0) return 0; //Nếu gặp hai số 0 và 0 thì thoát khỏi chương trình
        for (int i = 1; i<=n; i++) 
            cin >> a[i]; //Vị trí của các máy

        for (int i = 1; i<=m; i++)
            cin >> b[i]; //Vị trí của các khóm hoa

        sort(a + 1, a + n + 1); //Sắp xếp mảng a theo thứ tự tăng dần
        sort(b + 1, b + m + 1); //Sắp xếp mảng b theo thứ tự tăng dần

    }

Hàm chia nhị phân

#define INF (long long)1e16
long long solve() {
    long long L = 0, R = INF, mid;
    while (true) {
        if (L == R) return L;
        if (R - L == 1) return check(L) ? L : R;
        mid = (R + L)>>1;

        if (check(mid) == true) R = mid;
        else L = mid + 1;
    }
}

Giải thích

• Ta gọi khoảng $[L, R]$ là khoảng nghi ngờ chứa kết quả của bài toán.
• $mid = (R + L) >> 1$, đây là phép toán dịch bit phải, tương đương với $mid = (R + L)/2$ nhưng vì phép dịch bit có tốc độ xử lí nhanh hơn phép chia thông thường nhiều nên ta giữ nguyên.
• Khi $check(mid) = true$, tức là mid có là kết quả của bài toán (có thể chưa được tối ưu), theo nhận xét ở trên thì với $mid + 1$, $mid + 2$ đều có thể thu hoạch hết hoa, tuy nhiên, mục tiêu của chúng ta là tìm kết quả nhỏ nhất nên ta sẽ cho $R = mid$, khi đó khoảng nghi ngờ có nghiệm sẽ là $[L, mid]$, giả sử kết quả mid đã tối ưu thì nó vẫn nằm trong khoảng nghiệm đang xét.
• Khi $check(mid) = false$, tức là mid không phải là kết quả của bài toán, suy ra $mid - 1$, $mid - 2$,.. cũng không thể là kết quả của bài toán, vì vậy ta sẽ cho $L = mid + 1$, khoảng nghi ngờ có nghiệm sẽ trở thành $[mid + 1, R]$.
• Khi $L = R$, khoảng nghiệm nghi ngờ là $[L, L] = {L}$, lẽ dĩ nhiên L là nghiệm của bài toán và là nghiệm tối ưu.
• Khi $R - L = 1$, khoảng nghiệm nghi ngờ là $[L, L + 1] = {L, L + 1}$, khi đó ta ưu tiên kiểm tra $L$ trước bởi kết quả phải là nhỏ nhất, nếu $L$ không phải là nghiệm thì chắc chắn $R = L + 1$ là nghiệm tối ưu của bài toán.

Hàm kiểm tra kết quả

bool check(long long t) {
    long long vt = 0;
    long long tmp = 0;
    for (int i = 1; i<= n; i++) {
        tmp = 0;
        if (a[i] <= b[vt + 1]) tmp = a[i] + t;
        else {
        if (a[i] > b[vt + 1])
            if (a[i] - b[vt + 1] > t) return false;
            else {
                tmp = max(t - a[i] + 2*b[vt + 1], (t + a[i] + b[vt + 1])>>1);
            }
        }

        while (vt < m && b[vt + 1] <= tmp) vt++;
        if (vt == m) return true;
    }
    return false;
}

Giải thích

• Biến $vt$ lưu vị trí của khóm hoa trái nhất đã thu hoạch (hay số khóm hoa đã được thu hoạch), suy ra $vt + 1$ là vị trí của khóm hoa trái nhất chưa được thu hoạch.
• Trong bài này, ta sẽ coi mỗi máy sẽ thu những khóm hoa nhiều khóm hoa nhất có thể và không di chuyển giao nhau (gây mất nhiều thời gian hơn). Cũng có thể có trường hợp tồn tại máy nào đó không thu được gì cả.
• Ta xét lần lượt mỗi máy, gọi máy đang xét hiện tại có vị trí là a[i], ta có hai trường hợp lớn:
  1. Trường hợp 1: Khóm hoa trái nhất chưa được thu hoạch có vị trí lớn hơn hoặc bằng vị trí của máy đang xét (tức là $b[vt + 1] >= a[i]$), khi đó ta thu hoạch lần lượt các khóm hoa có chỉ số là $vt + 1, vt + 2,...$ cho đến khi hết thời gian.

2. Trường hợp 2: Khóm hoa trái nhất chưa được thu hoạch có vị trí nhỏ hơn vị trí của máy đang xét (tức là $b[vt + 1] < a[i]$).

• Trường hợp 2, máy thu hoạch có hai cách di chuyển:
  1. Máy thu hoạch di chuyển đến và thu hoạch khóm hoa trái nhất chưa thu hoạch (khóm hoa thứ $vt + 1$), rồi thu hoạch các khóm hoa có chỉ số $vt + 2, vt + 3,...$ cho đến khi hết thời gian.

2. Máy thu hoạch di chuyển và thu hoạch khóm hoa nào đó ở bên phải rồi thu hoạch dần về khóm hoa thứ $vt + 1$, tất nhiên là phải đảm bảo việc có đủ thời gian để lùi về khóm hoa thứ $vt + 1$.

• Ta gọi $tmp$ là "mốc thu hoạch" tức là vị trí lớn nhất mà máy thu hoạch có thể đến được ở cả hai cách di chuyển, khi đã tìm được mốc thu hoạch, ta chỉ cần kiểm tra lần lượt các khóm hoa kể từ khóm hoa thứ $vt + 1$ trở đi, khóm hoa nào có vị trí nhỏ hơn mốc thu hoạch tức là sẽ được thu hoạc bởi máy đang xét khi di chuyển tối ưu, cũng có thể không có khóm hoa nào có vị trí nhỏ hơn mốc thu hoạch, khi đó máy đang xét không thu hoạch được gì cả, việc thu hoạch để lại cho các máy phía sau.
• Xét trường hợp 1: $b[vt + 1] >= a[i]$, ta có thời gian di chuyển $t = tmp - a[i]$ suy ra cmốc thu hoạch $tmp = a[i] + t$.
• Xét trường hợp 2:
  1. Ta cần phải có điều kiện $a[i] - b[vt + 1] <= t$ nghĩa là máy đủ thời gian để di chuyển và thu hoạch được khóm hoa chưa được thu hoạch trái nhất (khóm hoa có chỉ số $vt + 1$), bởi nếu máy đang xét không thể thu hoạch được nó thì đương nhiên các máy phía sau cũng không đủ thời gian để thu hoạch được khóm hoa có chỉ số vt + 1. Tóm lại, nếu thoả mãn điều kiện thì ta tiếp tục xét các máy tiếp theo, nếu không thì có nghĩa là không đủ thời gian (hàm trả về $false$).
  2. Ở cách di chuyển thứ nhất, ta có thời gian di chuyển $t = a[i] - b[vt + 1] + tmp - b[vt + 1]$ suy ra mốc thu hoạch $tmp = t - a[i] + 2*b[vt + 1]$.
  3. Ở cách di chuyển thứ hai, ta có thời gian di chuyển $t = tmp - a[i] + tmp - b[vt + 1]$ suy ra mốc thu hoach $tmp = (t + a[i] + b[vt + 1])/2 = (t + a[i] + b[vt + 1])>>1$.
  4. Tổng hợp cả hai cách di chuyển, ta có mốc thu hoạch lớn nhất của cả hai trường hợp là $tmp = max(t - a[i] + 2*b[vt + 1], (t + a[i] + b[vt + 1])>>1)$.
• Sau khi tính được $tmp$ như trên, ta bắt đầu kiểm tra, sử dụng vòng lặp $while$, điều kiện là $vt < m$ tức là số khóm hoa đã thu hoạch nhỏ hơn số khóm hoa cần thu hoạch và $b[vt + 1] <= tmp$ tức là vị trí của khóm hoa trái nhất đang xét nhỏ hơn "mốc thu hoạch", nếu thoả mãn cả hai điều kiện thì tăng giá trị của $vt$ thêm $1$, tức là tăng chỉ số của khóm hoa đang xét (hay tăng số khóm hoa đã thu hoạch) thêm $1$ đơn vị.
• Nếu $vt = m$ có nghĩa là số khóm hoa đã thu hoạch bằng số khóm hoa bài cho, suy ra trong khoảng thời gian $t$ thì các máy đều có thể thu hoạch hết các khóm hoa, hàm trả về giá trị $true$. Ngược lại, nếu xét hết tất cả các máy mà hàm vẫn chưa trả về giá trị $false$ thì có nghĩa là không thể thu hoạch hết trong $t$ đơn vị thời gian, hàm trả về $false$.

Full code

#include <bits/stdc++.h>
#define INF (long long)1e16
using namespace std;
long long m,n, a[100005], b[100005];

void maximize(long long &x, long long y) {
    x = max(x,y);
}

bool check(long long t) {
    long long vt = 0; //chi so cua khom hoa trai nhat da thu hoach
    long long tmp = 0;
    for (int i = 1; i<= n; i++) {
        tmp = 0;
        if (a[i] <= b[vt + 1]) tmp = a[i] + t;
        else {
        if (a[i] > b[vt + 1])
            if (a[i] - b[vt + 1] > t) return false;
            else {
                tmp = max(t - a[i] + 2*b[vt + 1], (t + a[i] + b[vt + 1])>>1);
            }
        }

        while (vt < m && b[vt + 1] <= tmp) vt++;
        if (vt == m) return true;
    }
    return false;
}

long long solve() {
    long long L = 0, R = INF, mid;
    while (true) {
        if (L == R) return L;
        if (R - L == 1) return check(L) ? L : R;
        mid = (R + L)>>1;

        if (check(mid) == true) R = mid;
        else L = mid + 1;
    }
}
int main()
{
    //Lệnh tăng tốc độ đọc ghi của thuật toán
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("harvest.inp", "r", stdin); //Đọc input từ file harvest.inp
    freopen("harvest.out", "w", stdout); //In ra output tại file harvest.out

    while (cin >> n >> m) {

        if (n == 0 && m == 0) return 0;
        for (int i = 1; i<=n; i++)
            cin >> a[i];

        for (int i = 1; i<=m; i++)
            cin >> b[i];

        sort(a + 1, a + n + 1);
        sort(b + 1, b + m + 1);

        cout << solve() << " ";
    }
    return 0;
}

Nguồn bài tập: Phạm Văn Hạnh

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