Bạn cần ghi chi tiết cách tham lam.
- Gọi $ f (mid) $ là số lượng sách tối đa có thể lấy được khi có khoảng cách là $mid$. Ta sẽ sử dụng tham lam để tìm giá trị này
- Tìm kiếm nhị phân kết hợp với $f (mid)$ để tìm ra khoảng cách nhỏ nhất lớn nhất có thể để lấy được $k$ cuốn
- Độ phức tạp $O(nlog_n)$
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define el '\n'
void run_test()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
sort(all(a));
int lo = 0, hi = 1e15;
auto f = [&](int x) -> int
{
int res = 1, sus = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] - sus >= x) {res++; sus = a[i];}
}
return res;
};
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (f(mid) >= k) lo = mid + 1;
else hi = mid - 1;
}
cout << hi << el;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int test = 1;
// cin >> test;
while (test-- > 0)
{
run_test();
}
}
```
Thanhmay2005
Created at
2 likes