找到C++中修改後數組的最小值的最大可能值

在這個問題中，我們給定一個大小為 n 的陣列 arr[] 和一個數字 S。我們的任務是找到修改後的陣列的最小值的最大可能值。 p>

這裡是修改陣列的規則，

• 修改前後陣列元素總和應為S。

• 修改後的陣列中不允許有負值。

• 如果修改後的數組，需要數組的最小值最大化。

• 可以透過增加或減少陣列的任何元素來修改陣列。

使用這些約束，我們需要找到新陣列並傳回陣列中最小元素的最大值。

讓我們舉例來理解這個問題,

Input : arr[] = {4, 5, 6} S = 2
Output : 4

說明

修改後的陣列為{4, 5, 5}

解決方法

我們需要最大化修改後陣列的最小值。我們將使用二分搜尋來尋找最小值的最佳值，介於0（可能的最小值） 和arr_min（最大可能的）。我們將檢查差異以獲得最小的可能值。

一些特殊條件，

如果 S 大於陣列總和，則不可能有解決方案。

如果S 等於陣列總和，0 將是最小元素的值。

範例

說明我們解決方案工作原理的程式

#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
   int minVal = a[0];
   int arrSum = a[0];
   for (int i = 1; i < n; i++) {
      arrSum += a[i];
      minVal = min(a[i], minVal);
   }
   if (arrSum < S)
      return -1;
   if (arrSum == S)
      return 0;
   int s = 0;
   int e = minVal;
   int ans;
   while (s <= e) {
      int mid = (s + e) / 2;
      if (arrSum - (mid * n) >= S) {
         ans = mid;
         s = mid + 1;
      }
      else
         e = mid - 1;
   }
   return ans;
}
int main(){
   int a[] = { 4, 5, 6 };
   int S = 2;
   int n = sizeof(a) / sizeof(a[0]);
   cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S);
   return 0;
}

輸出

The maximum value of minimum element of the modified array is 4

以上是找到C++中修改後數組的最小值的最大可能值的詳細內容。更多資訊請關注PHP中文網其他相關文章！