Bài toán Vinyl và những chiếc tiêu

Bài toán

Vinyl là ninja có kĩ năng phi tiêu thượng thừa. Ngoài những tiêu làm bằng kim loại hình sao nhiều cạnh, Vinyl còn có những chiếc tiêu làm từ cây trúc.
Trong những lúc rảnh rỗi, Vinyl vào rừng chọn các cây trúc để làm tiêu. Những chiếc tiêu của Vinyl có độ dài L. Trước mặt anh bây giờ có N cây trúc, cây thứ i có độ cao là a[i].
Như vậy, có những cây trúc có thể tạo thành nhiều tiêu và không có các mẩu thừa. Nhưng cũng có các cây trúc khác sau khi tạo thành tiêu sẽ có các mẩu thừa.
Tất nhiên, Vinyl không muốn có các mẩu thừa này và anh ấy chỉ chặt các cây mà không tạo ra mẩu thừa.
Ví dụ: Có 3 cây trúc độ dài là 10, 11, 12 và độ dài tiêu L = 2.
132
Vinyl sẽ chặt cây 2 cây: cây 1 và cây 3. Tạo ra được 11 cây tiêu.
Yêu cầu: Hãy tính số tiêu mà Vinyl tạo được theo cách chặt cây của anh ấy.
Dữ liệu: Vào từ tệp DARTS.INP gồm:
• Dòng 1: Ghi số nguyên dương N và L (N, L ≤ 10^5).
• Dòng 2: Ghi N số nguyên dương a[i] (a[i] ≤ 10^9).
Kết quả: Ghi ra tệp DARTS.OUT số tiêu Vinyl có được theo cách chặt cây của anh ấy.

Thuật toán

Để giải bài toán này, ta có thể sử dụng thuật toán nhị phân để tìm độ dài của tiêu có thể chặt được từ các cây trúc. Sau đó, ta sẽ kiểm tra xem với mỗi độ dài tiêu đó, Vinyl có thể tạo được bao nhiêu tiêu.

Cụ thể, để tìm độ dài tiêu có thể chặt được từ các cây trúc, ta sử dụng thuật toán nhị phân để tìm giá trị L tối đa mà Vinyl có thể chặt được từ các cây trúc. Trong mỗi lần chạy thuật toán nhị phân, ta tính số tiêu có thể tạo ra từ độ dài L đó và kiểm tra xem nếu số tiêu đó lớn hơn hoặc bằng số tiêu cần tìm thì ta tăng giá trị L tối đa được chặt lên, ngược lại ta giảm giá trị L tối đa được chặt xuống.

Sau khi tìm được giá trị L tối đa được chặt, ta sẽ tính số tiêu có thể tạo ra từ độ dài L đó bằng cách duyệt qua các cây trúc và tính số lượng tiêu có thể tạo ra từ mỗi cây trúc. Nếu số lượng tiêu có thể tạo ra từ mỗi cây trúc lớn hơn 0 thì ta sẽ cộng các số lượng tiêu này lại với nhau để tính tổng số tiêu có thể tạo ra.

Độ phức tạp thời gian của thuật toán này là O(NlogM), trong đó N là số cây trúc và M là giá trị lớn nhất trong dãy a.

Cài đặt bài toán với Python

# đọc dữ liệu vào từ file darts.inp
with open('darts.inp', 'r') as f:
    n, l = map(int, f.readline().split())
    a = list(map(int, f.readline().split()))

# sắp xếp các cây trúc theo thứ tự tăng dần
a.sort()

# tìm số tiêu tối đa có thể tạo được
count = 0
i = 0
while i < n:
    # tìm cây trúc tiếp theo có thể sử dụng để làm tiêu
    j = i + 1
    while j < n and a[j] - a[i] < l:
        j += 1

    # nếu tìm được cây trúc thích hợp
    if j < n and a[j] - a[i] == l:
        count += 1
        i = j + 1  # chuyển sang cây trúc không thể sử dụng để làm tiêu
    else:
        i += 1

# ghi kết quả vào file darts.out
with open('darts.out', 'w') as f:
    f.write(str(count))

Cài đặt bài toán với C++

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

int main() {
    freopen("DARTS.INP", "r", stdin);
    freopen("DARTS.OUT", "w", stdout);

    int n, L;
    cin >> n >> L;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j + 1 < n && a[j + 1] - a[i] <= L) {
            j++;
        }
        ans += j - i;
    }

    cout << ans;

    return 0;
}