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

0

thinhduyson 4:48 p.m. 12 Tháng 3, 2024

from bisect import bisect
def find():
maxx=0
for i,nums in enumerate (a):
if nums+k>=a[n-1]:
return max(maxx,n-i)
else:
maxx=max(maxx,bisect(a,nums+k)-i)
t=int(input())
for _ in range(t):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
print(n-find())
ad hay bạn nào giúp mình tối ưu code này với ạ, run pypy3 thì nó out memories còn run python 3 thì out time ạ:>>

1 phản hồi

0

huyhau6a2 1:02 p.m. 23 Tháng 6, 2022

Sao có trường hợp mọi ngưòi làm y hệt mình mà vẫn tle nhỉ?

0

huyhau6a2 10:03 a.m. 23 Tháng 6, 2022 ← chỉnh sửa 3 →

đổi time lại 1,5s cho an toàn nha các bạn, 1s ác quá

0

huyhau6a2 6:51 p.m. 22 Tháng 6, 2022

đã chỉnh lại đề và bộ test, các bạn rejudge giúp mình nha!!!

0

nammai18 9:44 p.m. 20 Tháng 6, 2022

1
10 41
83 26 39 97 42 89 61 31 100 41
t thứ 7 của test 1 có sai không ạ ?
em ra 4 ạ

1 phản hồi

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)
1 phản hồi

1

huyhau6a2 12:45 p.m. 18 Tháng 12, 2021

tỉ lệ ac 8,3% hmm mình không biết nữa, hay bài này khó đến mức có mình và admin ac thôi sao ta

1

huyhau6a2 1:02 p.m. 14 Tháng 12, 2021

có vấn đê gì các bạn cứ gửi cho mình nhé, mình sẽ cố giải thích cho mọi người!

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 phản hồi