fork download
copy 
  1.  
  2.  
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. int findMax(vector<int> &v) {
  8.     int maxi = INT_MIN;
  9.     int n = v.size();
  10.     //find the maximum:
  11.     for (int i = 0; i < n; i++) {
  12.         maxi = max(maxi, v[i]);
  13.     }
  14.     return maxi;
  15. }
  16.  
  17. int calculateTotalHours(vector<int> &v, int hourly) {
  18.     int totalH = 0;
  19.     int n = v.size();
  20.     //find total hours:
  21.     for (int i = 0; i < n; i++) {
  22.         totalH += ceil((double)(v[i]) / (double)(hourly));
  23.     }
  24.     return totalH;
  25. }
  26.  
  27. int minimumRateToEatBananas(vector<int> v, int h) {
  28.     int low = 1, high = findMax(v);
  29.  
  30.     //apply binary search:
  31.     while (low <= high) {
  32.         int mid = (low + high) / 2;
  33.         int totalH = calculateTotalHours(v, mid);
  34.         if (totalH <= h) {
  35.             high = mid - 1;
  36.         }
  37.         else {
  38.             low = mid + 1;
  39.         }
  40.     }
  41.     return low;
  42. }
  43.  
  44. int main()
  45. {
  46.     vector<int> v = {7, 15, 6, 3};
  47.     int h = 8;
  48.     int ans = minimumRateToEatBananas(v, h);
  49.     cout << "Koko should eat atleast " << ans << " bananas/hr.\n";
  50.     return 0;
  51. }
  52.  
  53.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Koko should eat atleast 5 bananas/hr.
https://ideone.com/E9eUJF
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!