Bài toán trại nuôi bò

Bài toán trại nuôi bò

Nông trại MeKong vừa xây dựng xong một trại nuôi bò mới, trại gồm N chuồng bò được đặt dọc theo một đường thẳng ở các vị trí x₁, x₂…, x_N (0 ≤ x_i ≤ 10⁹).

Nông trại có M con bò được đưa vào nuôi ở N chuồng bò nêu trên, mỗi chuồng có không quá một con bò. Tuy nhiên vì M con bò của nông trại thuộc giống bò hung dữ nên để ngăn chặn các con bò có thể làm tổn thương nhau khi chúng ở khoảng cách quá gần, chủ nông trại muốn đưa các con bò vào các chuồng sao cho khoảng cách tối thiểu giữa hai con bò càng lớn càng tốt.

Yêu cầu: Hãy tìm khoảng cách tối thiểu lớn nhất giữa hai con bò có thể có.

Dữ liệu: Vào từ file văn bản TRAIBO.INP chứa các dòng dữ liệu sau:

• Dòng đầu tiên chứa số T (T ≤ 5) là số lượng bộ test (test cases).
• Sau đó là T nhóm dòng, mỗi nhóm gồm nhiều dòng:
• Dòng 1: chứa hai số N và M (2 ≤ N ≤ 10⁵, 2 ≤ M ≤ N);
• Trong N dòng tiếp theo, mỗi dòng chứa một số là vị trí của một chuồng bò. Lưu ý rằng các vị trí không sắp xếp theo thứ tự.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản TRAIBO.OUT gồm T dòng, mỗi dòng là khoảng cách tối thiểu lớn nhất giữa hai con bò tìm được ứng với T bộ test trong file input.

Ví dụ:

Cài đặt bài toán trại nuôi bò

Để tìm khoảng cách tối thiểu giữa hai con bò, ta có thể sử dụng phương pháp tìm kiếm nhị phân trên khoảng giá trị khoảng cách có thể có. Trong bài toán này, khoảng giá trị khoảng cách có thể có từ 0 đến khoảng cách xa nhất giữa hai chuồng bò.

Cụ thể, ta có thể thực hiện các bước sau:

1. Đọc dữ liệu từ file input.
2. Sắp xếp các vị trí của chuồng bò theo thứ tự tăng dần.
3. Tìm khoảng cách xa nhất giữa hai chuồng bò (tức khoảng cách giữa chuồng bò đầu tiên và chuồng bò cuối cùng).
4. Áp dụng phương pháp tìm kiếm nhị phân trên khoảng giá trị khoảng cách có thể có (từ 0 đến khoảng cách xa nhất giữa hai chuồng bò) để tìm khoảng cách tối thiểu giữa hai con bò. Trong quá trình tìm kiếm, với mỗi khoảng cách giả định, ta sẽ kiểm tra xem có thể đặt M con bò vào các chuồng bò sao cho khoảng cách giữa hai con bò lớn hơn hoặc bằng khoảng cách giả định đó hay không. Ta có thể thực hiện kiểm tra này bằng cách duyệt các chuồng bò theo thứ tự, đối với mỗi chuồng bò, ta kiểm tra xem có thể đặt con bò đầu tiên vào chuồng đó và đặt các con bò tiếp theo vào các chuồng tiếp theo sao cho khoảng cách giữa các con bò lớn hơn hoặc bằng khoảng cách giả định đó hay không.
5. Ghi kết quả vào file output.

Độ phức tạp của giải thuật này là O(N*log(D)), trong đó N là số lượng chuồng bò và D là khoảng cách xa nhất giữa hai chuồng bò.

Cài đặt bài toán trại nuôi bò với Python

# Hàm tính khoảng cách giữa 2 con bò
def distance(x, y):
    return abs(x - y)

# Hàm kiểm tra xem với khoảng cách d cho trước, liệu có thể đặt M con bò vào N chuồng bò hay không
def can_place_cows(x, cows, m, d):
    count = 1
    last_cow = cows[0]
    for i in range(1, len(cows)):
        if distance(cows[i], last_cow) >= d:
            count += 1
            last_cow = cows[i]
        if count == m:
            return True
    return False

# Hàm tìm khoảng cách tối thiểu lớn nhất giữa 2 con bò có thể có
def find_minimum_distance(cows, m):
    cows.sort() # Sắp xếp vị trí chuồng bò
    n = len(cows)
    left = 0
    right = cows[n - 1] - cows[0] # khoảng cách lớn nhất giữa 2 chuồng bò
    while left <= right:
        mid = (left + right) // 2
        if can_place_cows(mid, cows, m, n):
            left = mid + 1
            result = mid
        else:
            right = mid - 1
    return result

# Hàm đọc dữ liệu từ file và xuất kết quả
def solve():
    with open("TRAIBO.INP", "r") as f_in:
        t = int(f_in.readline())
        for i in range(t):
            n, m = map(int, f_in.readline().split())
            cows = []
            for j in range(n):
                cows.append(int(f_in.readline()))
            result = find_minimum_distance(cows, m)
            with open("TRAIBO.OUT", "a") as f_out:
                f_out.write(str(result) + "\n")

Cài đặt bài toán trại nuôi bò với C++

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

const int N = 1e5 + 5;

int n, m, a[N];

bool check(int d) {
    int cnt = 1;
    int last = a[1];
    for(int i = 2; i <= n; i++) {
        if(a[i] - last >= d) {
            cnt++;
            last = a[i];
        }
        if(cnt == m) return true;
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);

        int l = 1, r = 1e9, res = 0;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(check(mid)) {
                res = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        cout << res << endl;
    }
    return 0;
}