 # INFECT-Editorial

PRACTICE
Editorialist: Yogesh Yogendra

Medium

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.

1
5 3
1 2 8 4 9

3

# EXPLANATION:

This question was basically the variation of Aggressive Cow Problem of SPOJ.I have expained this question in a video, Link = https://youtu.be/Zwp6M5sl36Q , 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;
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;
}``````