Chia Cặp 1
Xem PDFLương Xiao Lin có \(n\) em gái có mức độ yêu thương lần lượt là \(a_1, a_2, ..., a_n\). Lương muốn chọn ra \(k\) cặp em gái rời nhau. Gọi \(x\) là chênh lệch lớn nhất giữa hai bạn trong một nhóm. Vì nếu chênh lệch mức độ yêu thương giữa 2 em gái quá lớn thì có thể một em sẽ buồn. Lương là anh trai cao cả, Lương không muốn em gái nào phải buồn. Do đó, Lương muốn x càng nhỏ càng tốt. Các bạn hãy tìm \(x\) giúp Lương nhé, Lương sẽ chia có các bạn 1 em gái nếu các bạn giúp Lương.
Input
-
Dòng đầu có 2 số nguyên \(n, k\).
-
Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\)
Output
- In ra một số nguyên là kết quả bài toán
Scoring
- Subtask \(1\) (\(100\%\) số điểm): \(2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2}\) và \(1 \leq a_i \leq 10^9\).
Example
Test 1
Input
6 3
1 4 3 7 11 9 Output
3Note
chúng ta chia cặp như sau: \((1, 3), (4, 7), (9, 11)\). Cặp có khoảng cách lớn nhất là \((4, 7)\) và \(7-4=3\).
Test 2
Input
6 2
1 4 3 7 11 9Output
2Note
chia cặp \((3, 4), (7, 9)\).
Test 3
Input
6 1
1 4 3 7 11 9Output
1Note
chia cặp \((3, 4)\).
Bình luận
'n' là số lượng phần tử
'k' là số lượng cặp số
n,k=map(int,input().split())
nhập mảng arr
arr=list(map(int,input().split()))
sắp sếp mảng arr
arr.sort()
def check(m):
# ta đoán m có phải là độ chênh lệch có đủ 'k' cặp
cnt=0
i=0
while i<=n-2:
# ta sẽ lấy arr[i] và arr[i+1]
#tính độ chênh lệch
cl= abs(arr[i] - arr[i+1])
#kiểm tra xem nó có thành 1 cặp được không
if cl <=m:
cnt+=1
i+=2
else:
i+=1
if cnt>=k:
return True
else:
return False
cần tìm độ chênh lệch nhỏ nhất mà phải đủ 'k' cặp, gọi là mini
mini=999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
ta dùng TKNP để tìm giá trị 'mini'
l=0;r=int(1e9)# 1e9 là 10 mũ 9
while l <= r:
# ta đoán m có phải là độ chênh lệch có đủ 'k' cặp
m=(l+r)//2
if check(m) == True:
mini=m
r=m-1
else:
l=m+1
print(mini)
:v
:v