Trouver la valeur maximale possible de la valeur minimale d'un tableau modifié en C++

Dans ce problème, on nous donne un tableau arr[] de taille n et un nombre S. Notre tâche est de trouver la valeur maximale possible de la valeur minimale du tableau modifié. p>

Voici les règles de modification du tableau,

• La somme des éléments du tableau avant et après modification doit être S.

• Aucune valeur négative n'est autorisée dans le tableau modifié.

• Si le tableau modifié doit maximiser la valeur minimale du tableau.

• Un tableau peut être modifié en ajoutant ou en soustrayant n'importe quel élément du tableau.

En utilisant ces contraintes, nous devons trouver le nouveau tableau et renvoyer la valeur maximale du plus petit élément du tableau.

Prenons un exemple pour comprendre ce problème,

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

Explication

Le tableau modifié est {4, 5, 5}

Solution

Nous devons maximiser la valeur minimale du tableau modifié. Nous utiliserons une recherche binaire pour trouver la meilleure valeur pour le minimum compris entre 0 (minimum possible) et arr_min (maximum possible). Nous vérifierons la différence pour obtenir la valeur la plus petite possible.

Quelques conditions particulières,

Si S est supérieur à la somme du tableau, il n'y a pas de solution possible.

Si S est égal à la somme du tableau, 0 sera la valeur du plus petit élément.

Exemple

Programme qui illustre le fonctionnement de notre solution

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

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!