Những chú ếch
Xem PDF
Đ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 2Output
2Note
Giải thích: cần đổi độ cao của hai chiếc bèo 2 và 5
Bình luận
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 ạ:>>
-
0
rodnguyen
7:35 p.m. 14 Tháng 3, 2024
←
đã chỉnh sửa
→
-
0
thinhduyson
4:05 p.m. 24 Tháng 3, 2024
8 bình luận nữaĐây nha bạn:
from bisect import bisect
def find(a, n, k):
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(a, n, k))
mình nộp code lên cũng bị như code của mình mà bạn, với của bạn là bạn truyền tham số vào chứ không có chỉnh sửa gì về mặt thuật toán hay tối ưu dữ liệu nên mình thấy có khác j đâu ạ