Những chú ếch

Tác giả:

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

Note

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

Bình luận

Mình thấy 2 ngày rồi chưa ai ac bài này nên mình xin chỉ dẫn khái quát: Vì ta chỉ cần xét độ cao của 2 chiếc bèo cao nhất và nhỏ nhất là ta có thể xem được là tất cả chú ếch có thể nói chuyện với nhau hay không:

   - Tìm kiếm nhị phân: trước tiên ta sort mảng lại, VD test "104 1 100 102 2" ==> "1 2 100 102 104". Với vị trí l thể sự thay đổi độ cao của các vị trí từ 1 đến l thì ta phải tìm số r có số hiệu nhỏ nhất sao cho A[r]>A[l]+k. Với vị trí r thể hiện sự thay đổi độ cao của các vị trí từ n về r. Vậy chênh lệch độ cao hai chiếc bèo cao nhất và nhỏ nhất là A[r-1]-A[l+1]
   - Hai con trỏ: dựa vào tìm kiếm nhị phân để suy luận ra cách dùng 2 con trỏ cho bài này

Mong các bạn có thể dựa vào gợi ý này mà ac bài này dễ hơn!

1

minhtuanitk20 11:38 a.m. 2 Tháng 12, 2021

thanks

1

huyhau6a2 1:55 p.m. 3 Tháng 12, 2021

Mình thấy hơi thất bại khi chả ai làm được bài của mình. Huhuhu!

1

nguyendanghau2006 6:52 p.m. 13 Tháng 12, 2021

có thêm anh stack_queue_4977 nữa .-.

1

huyhau6a2 10:56 a.m. 14 Tháng 12, 2021

Nói như không mình nhờ admin ra mà admin ac là chuyện thường

1

minhtuanitk20 2:11 p.m. 3 Tháng 12, 2021

có anh jump ac

1

huyhau6a2 2:14 p.m. 3 Tháng 12, 2021

mình nhờ admin ra mà, ac là chuyện thường, ai đó ac bài này cho mình vui tí đi!

8 bình luận nữa