PROBLEM LINK:
PRACTICE
Editorialist: Yogesh Yogendra
DIFFICULTY:
Medium
PREREQUISITES:
Binary Search
PROBLEM:
Yogesh has built a new hospital, with N(2<= N <= 100,000) beds. The beds are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).
Their are C(2<= C <=N) number of COVID infected persons. To prevent the further infections, you have to assign the beds to infected persons in such a way that the minimum distance between any two of them is as large as possible.
What is the largest minimum distance?
Constraints
(2 <= N <= 100,000)
(0 <= xi <= 1,000,000,000)
(2 <= C <= N)
Input
t – the number of test cases, then t test cases follows.
- Line 1: Two space-separated integers: N and C
- Line 2: N space seperated integers representing the bed locations i.e xi
Output
For each test case output one integer: the largest minimum distance.
Sample Testcase 1:
Input
1
5 3
1 2 8 4 9
Output:
3
EXPLANATION:
This question was basically the variation of Aggressive Cow Problem of SPOJ.I have expained this question in a video, Link = Aggressive Cows | Love Babbar DSA Sheet | GFG | FAANG🔥| Placement | SPOJ | Binary Search | Important - YouTube , go and have a look.
SOLUTION:
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define ps(x,y) fixed<<setprecision(y)<<x
#define mod 1000000007
#define w(x) int x; cin>>x; while(x--)
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
w(T)
{
int n,c;
cin>>n>>c;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int lb = 1;
int ub = 1e9;
int ans = 0;
while(lb<=ub){
int mid = (lb+ub)/2;
int cow = 1;
int prev = a[0];
for(int i=1;i<n;i++){
if(a[i]-prev>=mid){
cow++;
prev = a[i];
if(c==cow) break;
}
}
if(cow==c) {
ans = mid;
lb = mid + 1;
}
else ub = mid - 1;
}
cout<<ans<<endl;
}
return 0;
}