fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. bool canDistribute(vector<int>& arr, int k, int mid) {
  8.     int n = arr.size();
  9.     int required = 0;
  10.  
  11.     for (int i = 0; i < n; i++) {
  12.         if (arr[i] < mid) {
  13.             required += (mid - arr[i]);
  14.         }
  15.     }
  16.  
  17.     return required >= k;
  18. }
  19.  
  20. int minimizeMaxElement(vector<int>& arr, int k) {
  21.     int n = arr.size();
  22.     int low = *max_element(arr.begin(), arr.end());  // The minimum possible answer
  23.     int high = low + k;  // The maximum possible answer
  24.     int result = high;
  25.  
  26.     while (low <= high) {
  27.         int mid = low + (high - low) / 2;
  28.  
  29.         if (canDistribute(arr, k, mid)) {
  30.             result = mid;
  31.             high = mid - 1;
  32.         } else {
  33.             low = mid + 1;
  34.         }
  35.     }
  36.  
  37.     return result;
  38. }
  39.  
  40. int main() {
  41.     vector<int> arr = {7, 5, 1, 9, 1};
  42.     int k = 25;
  43.  
  44.     int result = minimizeMaxElement(arr, k);
  45.     cout << "Minimum possible maximum element: " << result << endl;
  46.  
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Minimum possible maximum element: 10
https://ideone.com/17zIzM
language:
C++14 (gcc 8.3)
created:
10 hours 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!