---
# System prepended metadata

title: Cày trâu bài 8 (tham lam)

---

# Cày trâu bài 8 (tham lam)
Tạo mảng ***d*** là mảng khoảng cách giữa các phần tử của mảng ***a*** sau khi sort

Chọn mỗi phần tử ***d[i]*** làm phần tử gốc

Đếm xem có bao nhiêu cặp phân biệt có khoảng khoảng cách nhỏ hơn gốc ***d[i]*** đã chọn

Nếu số lượng cặp đếm được lớn hơn hoặc bằng ***k*** và ***d[i]*** nhỏ hơn hoặc bằng ***res*** thì lưu ***res = d[i]***

``` c
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long

ll n, k, a[300005], d[300005], x, dem, res = 1e18, i, j;
bool ok[100005];

int main() {
	cin >> n >> k;
	for (i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + 1 + n);
	for (i = 1; i < n; ++i) d[i] = abs(a[i] - a[i + 1]);
	for (i = 1; i < n; ++i) {
		x = d[i];
		dem = 1;
		ok[i] = ok[i + 1] = ok[i - 1] = 1;
		for (j = 1; j < n; ++j)
		if (!ok[j] && d[j] <= x) {
			++dem;
			ok[j] = ok[j + 1] = ok[j - 1] = 1;
		}
		if (dem >= k) res = min(res, x);
		for (j = 1; j < n; ++j) ok[j] = 0;
	}
	cout << res;
}
```