Aggressive cow (binary serch
user_6075971
plain_text
3 years ago
1.3 kB
4
Indexable
#include <iostream>
using namespace std;
bool check(int arr[], int n, int m, int mid)
{
// AGGERASIVE COW PROBLEM
int cow = 1;
int first_pos = arr[0];
for (int i = 0; i < n; i++)
{
if (arr[i] - arr[0] >= mid)
{
cow++;
if (cow == m)
{
return true;
}
first_pos = arr[i];
}
}
return false;
}
int possible_min(int arr[], int n, int m)
{
int sum = arr[n - 1] - arr[0];
int s = 0;
int ans = -1;
int e = sum;
int mid = (s + e) / 2;
while (s <= e)
{
if (check(arr, n, m, mid))
{
ans = mid;
s = mid + 1;
}
else
{
e = mid - 1;
}
mid = (s + e) / 2;
}
return ans;
}
int main()
{
int n;
int m;
cout << "ENTER THE SIZE OF ARRAY--->";
cin >> n;
int arr[100];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
sort(arr, arr + n);
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
cout << "ENTER THE COUNT OF AGGRESIVE COW--->";
cin >> m;
cout << endl;
cout << "ANSWER--->" << possible_min(arr, n, m);
return 0;
Editor is loading...