Maison > développement back-end > C++ > Trouver la valeur maximale possible de la valeur minimale d'un tableau modifié en C++

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Libérer: 2023-09-09 22:17:02
avant
1420 Les gens l'ont consulté

Trouver la valeur maximale possible de la valeur minimale dun 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
Copier après la connexion

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 arrmin (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;
}
Copier après la connexion

Sortie

The maximum value of minimum element of the modified array is 4
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal