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();
}
}
```
To Maximize the minimum difference between the position of two consecutive. We can apply Binary Search on possible answers.
Here's Why-
We can always apply binary search on possible answers when we know a threshold value and we can prove that there lies no answer strictly greater than this threshold.
As we care about the difference between consecutive positions so sort the position array.
Let the Maximum minimum difference we can achieve be d.
here, for any n, k and position array.
\\(\\;\\Rightarrow\\) Claim 1: Minimum possible value of d will be 1.
\\(\\;\\Rightarrow\\) Proof 1: As given no two book can occupy the same position so the minimum possible difference will be 1.
\\(\\;\\Rightarrow\\) Claim 2: Maximum possible value of d will be difference between the maximum and minimum position.
\\(\\;\\Rightarrow\\) Proof 2: Maximum difference we can achieve is maximum_position - minimum_position i.e. k == 2
if k > 2, the minimum difference will be less than maximum_position - minimum_position.
as the other available positions are lying between these so the difference decreases.
Now we can apply binary search to this range and for every possible answer (let say x) we pick the books such that the difference between every two consecutive book position is greater than or equal to x.
We can use lowerbound to find such positions.
Time complexity: \\(O(n \\log n + k \\log n \\log D)\\) \\(\\quad\\)(\\(D\\) is the interval length \\(a[n-1] - a[0]\\)).
Auxiliary Space complexity: \\(O(1)\\)
```cpp
#include <bits/stdc++.h>
using namespace std;
int lowerbound(vector<int>& a, long long k){
int l = 0, r = a.size()-1;
while (r - l + 1 > 1){
int m = l + (r-l)/2;
if (a[m] >= k){r = m;}
else {l = m+1;}
}
if (a[r] < k){return -1;}
return r;
}
int CanWe(vector<int>& a, int m, int k){
long long num = a[0];
int l = 1, r = a.size()-1;
while (k > 0 && l <= r){
int x = lowerbound(a, num + m);
if (x == -1){return false;}
l = x; num = a[l]; k--;
}
return true;
}
int main(){
int n, k; cin >> n >> k;
vector<int> a(n);
for (int i = 0; i< n; i++){cin >> a[i];}
sort(a.begin(), a.end());
int l = 1, r = a[n-1]-a[0];
while (r - l + 1 >= 1){
int m = l + (r - l)/2;
if (CanWe(a, m, k-1)){l = m + 1;}
else {r = m - 1;}
}
cout << r << '\n';
}
```
Thanhmay2005
Created at
3 likes
prashant_tak_04
Created at
0 likes