Hướng giải của Planting Trees

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: Planting Trees (Trồng Cây Khoảng Cách Lớn Nhất)

Phân tích bài toán

Bài toán yêu cầu đặt \(M\) cây vào \(N\) vị trí tọa độ cho trước sao cho khoảng cách nhỏ nhất giữa hai cây bất kỳ là lớn nhất (Bài toán kinh điển Aggressive Cows / Chặt nhị phân kết quả).

Thuật toán chặt nhị phân
  1. Sắp xếp mảng tọa độ \(x_1 < x_2 < \dots < x_N\).
  2. Không gian tìm kiếm khoảng cách \(D \in [1, x_N - x_1]\).
  3. Hàm kiểm tra check(D): Tham lam đặt cây đầu tiên tại \(x_1\), các cây tiếp theo đặt tại vị trí \(x_j \ge \text{last\_pos} + D\). Nếu đặt được \(\ge M\) cây thì \(D\) khả thi.
  4. Chặt nhị phân tìm \(D\) lớn nhất thỏa mãn.

Độ phức tạp thuật toán

  • Thời gian: \(O(N \log N + N \log(\max X))\).
  • Không gian bộ nhớ: \(O(N)\).

Mã nguồn C++ tham khảo

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool can_place(const vector<long long>& x, int m, long long d) {
    int placed = 1;
    long long last = x[0];
    for (size_t i = 1; i < x.size(); ++i) {
        if (x[i] - last >= d) {
            placed++;
            last = x[i];
            if (placed >= m) return true;
        }
    }
    return placed >= m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<long long> x(n);
    for (int i = 0; i < n; ++i) cin >> x[i];
    sort(x.begin(), x.end());

    long long low = 1, high = x.back() - x.front(), ans = 1;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        if (can_place(x, m, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    cout << ans << "\n";
    return 0;
}

Nhận xét

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