C++ で変更された配列の最小値の可能な最大値を求める

この問題では、サイズ n と数値 S の配列 arr[] が与えられています。私たちのタスクは、変更された配列の最小値の 可能な最大値を見つけることです。 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 中国語 Web サイトの他の関連記事を参照してください。