C++で変更された配列の最小値の可能な最大値を見つけます

この問題では、サイズnと数値Sの配列arr []が与えられます。私たちのタスクは、変更された配列の最小値の可能な最大値を見つけることです。 。

アレイを変更するためのルールは次のとおりです

• 変更前と変更後の配列要素の合計の差は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