Hướng giải của Thả lưới cá

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Lời giải: Thả lưới cá

Ý tưởng

Bài toán hoàn toàn tương tự "Bò trong chuồng". Sắp xếp vị trí tăng dần rồi chọn $K$ vị trí sao cho khoảng cách giữa hai vị trí liên tiếp $\ge D$. Đây là bài toán lớn nhất mà khoảng cách nhỏ nhất đạt được.

Thuật toán

Sắp xếp $p$.
Cận dưới: $1$.
Cận trên: $p_N - p_1$.
Thử $D$:
- Với con trỏ chạy qua mảng, đếm số lưới: bắt đầu từ vị trí 0. Với mỗi vị trí tiếp theo, nếu $p_i - last \ge D$ thì đặt lưới, last = p_i, tăng biến đếm.
- Nếu $\ge K$: khả thi → tăng $lo = D$.
- Ngược lại: giảm $hi = D - 1$.

Độ phức tạp

$Mỗi lần kiểm tra: $O(N)$. Tổng: $O(N \log(10^9))$.

Mã nguồn tham khảo

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

bool check(const vector<long long>& p, int K, long long D) {
    int cnt = 1;
    long long last = p[0];
    for (size_t i = 1; i < p.size(); i++) {
        if (p[i] - last >= D) { cnt++; last = p[i]; }
    }
    return cnt >= K;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<long long> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    sort(p.begin(), p.end());
    long long lo = 1, hi = p.back() - p.front();
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (check(p, K, mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.