Finden Sie den maximal möglichen Wert des minimalen Werts eines geänderten Arrays in C++

In diesem Problem erhalten wir ein Array arr[] der Größe n und eine Zahl S. Unsere Aufgabe besteht darin, den maximal möglichen Wert des Minimalwerts des geänderten Arrays zu finden. p>

Hier sind die Regeln zum Ändern des Arrays:

• Die Summe der Array-Elemente vor und nach der Änderung sollte S sein.

• Im geänderten Array sind keine negativen Werte zulässig.

• Wenn das geänderte Array den Mindestwert des Arrays maximieren muss.

• Ein Array kann durch Hinzufügen oder Entfernen eines beliebigen Elements des Arrays geändert werden.

Anhand dieser Einschränkungen müssen wir das neue Array finden und den Maximalwert des kleinsten Elements im Array zurückgeben.

Nehmen wir ein Beispiel, um dieses Problem zu verstehen,

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

Erklärung

Das geänderte Array ist {4, 5, 5}

Lösung

Wir müssen den Mindestwert des geänderten Arrays maximieren. Wir verwenden eine binäre Suche, um den besten Wert für das Minimum zu finden, das zwischen 0 (dem kleinstmöglichen Wert) und arr_min (dem größtmöglichen Wert) liegt. Wir werden die Differenz prüfen, um den kleinstmöglichen Wert zu erhalten.

Einige Sonderbedingungen:

Wenn S größer als die Summe des Arrays ist, ist keine Lösung möglich.

Wenn S gleich der Summe des Arrays ist, ist 0 der Wert des kleinsten Elements.

Beispiel

Programm, das veranschaulicht, wie unsere Lösung funktioniert

#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;
}

Ausgabe

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

Das obige ist der detaillierte Inhalt vonFinden Sie den maximal möglichen Wert des minimalen Werts eines geänderten Arrays in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!