# Hướng Dẫn
## Mô tả bài toán
Bài toán yêu cầu tìm giá trị thứ `k` trong dãy `|A[i] - A[j]|` sau khi sắp xếp không giảm với mọi `1 ≤ i < j ≤ n`.
## Giải thích giải thuật
1. **Ý tưởng chính:**
- Sử dụng tìm kiếm nhị phân trên kết quả
- Với mỗi giá trị `mid`, ta kiểm tra xem có bao nhiêu cặp số có hiệu không vượt quá `mid`
- Dựa vào số lượng cặp số tìm được, ta điều chỉnh khoảng tìm kiếm
2. **Chi tiết giải thuật:**
- Đầu tiên, sắp xếp mảng `A` để tối ưu việc đếm
- Thực hiện tìm kiếm nhị phân trên đoạn `[0, max(A) - min(A)]`
- Với mỗi giá trị `mid`:
+ Với mỗi phần tử `A[i]`, tìm số lượng phần tử `A[j]` (j > i) sao cho `|A[j] - A[i]| <= mid`
+ Do mảng đã sắp xếp, ta chỉ cần tìm vị trí đầu tiên lớn hơn `A[i] + mid`
+ Sử dụng `upper_bound()` để tìm vị trí này một cách hiệu quả
3. **Hàm `dem(mid)`:**
- Đếm số lượng cặp `(i, j)` thỏa mãn `|A[i] - A[j]| <= mid`
- Nếu số lượng cặp < `k`: cần tăng `mid`
- Nếu số lượng cặp >= `k`: có thể thử giảm `mid`
## Độ phức tạp
- **Thời gian**: O(n log n × log M)
+ O(n log n) cho việc sắp xếp mảng
+ O(log M) lần tìm kiếm nhị phân, với M là hiệu max(A) - min(A)
+ Mỗi lần đếm mất O(n log n)
- **Không gian**: O(n) để lưu mảng đầu vào
## Code
```cpp
/*
@author longvuuuu
@github kuronight29
*/
#include <bits/stdc++.h>
#define taskname ""
#define ll long long
#define pb push_back
using namespace std;
int main() {
if(fopen((string(taskname) + ".inp").c_str(), "r") != NULL) {
freopen((string(taskname) + ".inp").c_str(), "r", stdin);
freopen((string(taskname) + ".out").c_str(), "w", stdout);
}
ll n, k;
cin >> n >> k;
ll res = 0;
vector<ll> A(n);
for(ll i = 0; i < n; ++i) {
cin >> A[i];
}
auto dem = [&](ll mid) {
ll res = 0;
for(ll i = 0; i < n; ++i) {
res += upper_bound(A.begin() + i + 1, A.end(), A[i] + mid) - (A.begin() + i + 1);
}
return res;
};
sort(A.begin(), A.end());
ll left = 0, right = A[n-1] - A[0];
while(left < right) {
ll mid = left + (right - left) / 2;
if(dem(mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
cout << left << endl;
return 0;
}
longvuuu
Created at
5 likes