PROBLEM LINK
problem
Author:
a0n0k0i0t
Tester:
a0n0k0i0t
Editorialist:
jitinonline
DIFFICULTY
Medium
EXPLANATION
Take a double array to store all wire lengths. Now binary search for the maximum length from 0 to maximum of all lengths. The length is acceptable if the total number of pieces the number of pieces is p. If the number of pieces obtained by length l is more than or equal to p then binary search over right half else binary search over left half.
Repeat the binary search till precision of 6 decimal places is achieved.
SOLUTION
//Question: Wire cutting
//Solution: Application of binary search
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
bool good(vector<double> arr, double m, ll p)
{
ll pieces = 0;
for (auto i : arr)
{
pieces += (ll)((double)i / m);
}
return (pieces >= p);
}
void solve()
{
ll w, p;
cin >> w >> p;
vector<double> arr(w);
for (int i = 0; i < w; i++)
{
cin >> arr[i];
}
//Using binary search from 0 to max length of any wire
double l = 0, r = *max_element(arr.begin(), arr.end()), m;
for (int i = 0; i < 100; i++)
{
m = l + (r - l) / 2;
if (good(arr, m, p))
{
l = m;
}
else
{
r = m;
}
}
cout << fixed<<setprecision(6) << l;
}
signed main()
{
solve();
return 0;
}