PROBLEM LINK:
Editorialist: pdwivedi294
DIFFICULTY:
EASY MEDIUM
PREREQUISITES:
Binary Search
PROBLEM:
As you are aware that your neighbouring country is under the war. You being the chief securtiy adivser of your country are worry about security of your country.
So you decided to export x unit of weapon in your border area from your security center. To do so you have n kind of transport vehicles where ith vehicle take ai time for one trip. Each vehicle in one trip are capable of transporting y unit of weapon.
You are task is to find what is minimum time to transport x unit of weapon to the border area.
Explanation
Since in one trip maximum y unit of weapon can be transported so to transport total of x unit weapon there should be total ceil(x/y) trips.
In order to find minimum time to complete required trips we can use hit and trial that can we complete the required trip in t =1s or 2s, or 3s as we get the requried time we can output it.
This approch of finding time for given constraints can be lead to Time Limit Exceeded.
In optimization we can apply binary search to find minimum time setting low time as 0 and maximum time as 1e15. comparing mid we can sync the search space.
Code
int n, x, y;
cin >> n >> x >> y;
vector<ll> arr(n);
loop(i, 0, n){
cin >> arr[i];
}
ll total_trip = ceil(double(x)/y);
ll low = 0, high = 1e15;
ll res=100;
while(low < high){
ll mid = (low+ (high-low)/2);
if(mintime(arr, mid) >= total_trip){
high = mid;
res = mid;
}
else low = mid+1;
}
cout << res << endl;