Những chú ếch

Xem PDF
Tác giả:
huyhau6a2
Dạng bài
Điểm: 350 (p) Thời gian: 2.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong hồ có \(n\) chú ếch, mỗi chú đứng trên \(1\) chiếc bèo khác nhau. Chú ếch thứ \(i\) đừng trên chiếc bèo độ cao \(A[i]\). Biết hai chú ếch \(i\) và \(j\) có thể nói chuyện với nhau \((1\le i,j\le n)\) khi \(|A[i]-A[j]|\le k\). Hãy tìm cách đổi độ cao của ít chiếc bèo nhất sao cho tất cả chú ếch có thể nói chuyện với nhau.

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase

  • \(t\) block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa hai số \(n\) và \(k(n\le 10^5,k\le 10^9)\)

  • Dòng thứ hai chứa gồm \(n\) số thể hiện độ cao của những chiếc bèo

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm

Example

Test 1

Input 
1
5 4 
104 1 100 102 2
Output 
2
Note

Giải thích: cần đổi độ cao của hai chiếc bèo 2 và 5

Bình luận


  • 2
    huyhau6a2    8:45 p.m. 17 Tháng 1, 2022 ← đã chỉnh sửa

    Alo mọi người tới giờ mình up hint cuối cho bài này rồi, thường hint đầu mình sẽ cho kiểu các bạn tư vận dụng, hint sau nếu ít người ac thì mình mới up nha:

    • Đầu tiên ta phân tích thì thấy ta chỉ cần quan tâm tới chiếc bèo thấp và cao nhất thôi, những cái giữa không quan trọng để xét xem có thỏa mãn hay không
    • Vậy ta chỉ cần thay đổi độ cao của những chiếc bèo từ trái sang theo độ cao nhỏ đến lớn hoặc từ phải sang theo độ cao từ lớn về bé
    • Phân tích thực chất đơn giản thế thôi, giờ tới phần code:
    • Đầu tiên để xét thay đổi độ cao chắc chắn phải sort độ cao
    • Sau đó, khi xét từ trái sang, khi thay đổi độ cao của chiếc bèo từ 1->l thì r là số bèo cần thay đổi nhỏ nhất từ phải về sao cho thỏa mãn tất cả chú ếch có thể nói chuyện với nhau. Giá trị r để tìm r lớn nhất thỏa mãn có thể dùng chặt nhị phân. Độ khó: O(2n.log(n))
    • Ngoài ra, khi phân tích thêm thì khi l tăng thì r cũng tăng theo, điều đó ta có thể dùng 2 con trỏ theo chiều l, r đều ở nút đầu, sau đó khi l tăng thì ta sẽ tính r tăng theo sao cho thỏa mãn. Độ khó O(n.log(n)+2n)
    • 8 bình luận nữa