Practice › Binary Search
Aggressive Cows
Hard · Binary Search · Asked at Amazon, Google, Flipkart, Directi
There are n stalls at given positions. Place c cows in different stalls so that the minimum distance between any two cows is as large as possible. Print that largest minimum distance.
Input
First line: n c. Second line: n stall positions.
Output
The largest possible minimum distance.
Constraints
- 2 ≤ c ≤ n ≤ 10^5
- 0 ≤ position ≤ 10^9, positions are distinct
Sort the stalls, binary search on the distance and place cows greedily.
Example 1
Input
5 3 1 2 8 4 9
Output
3
Example 2
Input
3 2 10 1 2
Output
9
Hints
- If cows can be placed with minimum gap d, they can also be placed with any smaller gap.
- Sort the stalls. For a fixed d, place cows greedily: first stall, then every next stall at least d away. Binary search the largest d that fits c cows.
Approach
After sorting, canPlace(d) puts a cow in the first stall and then in each stall at least d past the last cow. Taking the earliest possible stall each time is optimal, because it leaves the most room for the rest. canPlace is true up to some value and false beyond it, so binary search d between 1 and last − first for the largest feasible value.
Complexity: O(n log n + n log(range)) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, c;
cin >> n >> c;
vector<long long> s(n);
for (auto &x : s) cin >> x;
sort(s.begin(), s.end());
auto canPlace = [&](long long d) {
int cows = 1;
long long last = s[0];
for (int i = 1; i < n; i++)
if (s[i] - last >= d) {
cows++;
last = s[i];
}
return cows >= c;
};
long long lo = 1, hi = s[n - 1] - s[0];
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (canPlace(mid)) lo = mid;
else hi = mid - 1;
}
cout << lo << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, c = data[0], data[1]
s = sorted(data[2 : 2 + n])
def can_place(d):
cows, last = 1, s[0]
for x in s[1:]:
if x - last >= d:
cows += 1
last = x
if cows >= c:
return True
return cows >= c
lo, hi = 1, s[-1] - s[0]
while lo < hi:
mid = (lo + hi + 1) // 2
if can_place(mid):
lo = mid
else:
hi = mid - 1
print(lo)Java solution
import java.util.*;
public class Main {
static long[] s;
static int c;
static boolean canPlace(long d) {
int cows = 1;
long last = s[0];
for (int i = 1; i < s.length; i++)
if (s[i] - last >= d) {
cows++;
last = s[i];
}
return cows >= c;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
c = sc.nextInt();
s = new long[n];
for (int i = 0; i < n; i++) s[i] = sc.nextLong();
Arrays.sort(s);
long lo = 1, hi = s[n - 1] - s[0];
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2;
if (canPlace(mid)) lo = mid;
else hi = mid - 1;
}
System.out.println(lo);
}
}