C++-Programm zum Entfernen des kleinsten Elements auf beiden Seiten, sodass der 2*-Mindestwert größer als der Maximalwert ist

Das Problem besteht darin, Elemente von beiden Seiten einer Liste von Ganzzahlen so zu entfernen, dass 2*min größer als max ist.

vector<int> arr = {250, 10, 11, 12, 19, 200};
res = solve(arr);

Wir können Brute-Force-Methoden anwenden. Wir können alle möglichen Erfüllungen ausprobieren und das längste Subarray finden, das die Bedingung 2*min > max erfüllt. Wir können auch dynamische Programmiermethoden verwenden, um alle möglichen übermäßigen und unerwünschten Subarray-Kombinationen auszuprobieren.

Beispiel (mit Vektor-ADT)

Angenommen, wir haben ein Array wie „[250, 10, 11, 12, 19, 200]“. Um die beste Lösung zu erhalten, müssen wir die Elemente [250, 200] entfernen, um ein Array [10, 11, 12, 19] zu bilden, wobei min 10 und max 19 ist. Daher 2*10 > 19. Wir drucken aus einem Array, die Ausgabe ist also 2.

Unten finden Sie ein C++-Programm, das beschreibt, wie eine Mindestanzahl von Elementen aus einem Array entfernt wird, sodass das Doppelte des Mindestwerts größer als der Maximalwert ist -

#include <iostream>
#include <vector>
using namespace std;
int solve(vector<int> arr) {
   int startIndex = 0, endIndex = 0;
   bool foundAnAnswer = false;
   for (int start=0; start<arr.size(); start++) {
      int min = INT32_MAX, max = INT32_MIN;
      for (int end=start; end<arr.size(); end++) {
         if (arr[end] < min) min = arr[end];
         if (arr[end] > max) max = arr[end];
         if (2*min <= max) break;
         if (end - start > endIndex - startIndex || !foundAnAnswer) {
            startIndex = start;
            endIndex = end;
            foundAnAnswer = true;
         }
      }
   }
   if (!foundAnAnswer) return arr.size();
   return (arr.size() - (endIndex - startIndex + 1));
}
int main() {
   vector<int> arr = {250, 10, 11, 12, 19, 200};
   cout << solve(arr);
   return 0;
}

Ausgabe

2

Beispiel (ohne Vektor-ADT)

Hier ist ein C++-Programm, das beschreibt, wie man eine Mindestanzahl von Elementen aus einem Array entfernt, sodass das Doppelte des Mindestwerts größer als der Maximalwert ist, jedoch ohne Verwendung von Vector ADT -

#include <iostream>
using namespace std;
int min(int a, int b) {return (a < b)? a : b;}
int min(int arr[], int low, int high)
   {
      int minimum = arr[low];
      for (int i=low+1; i<=high; i++)
      if (minimum > arr[i])
         minimum = arr[i];
      return minimum;
   }
int max(int arr[], int low, int high)
   {
      int maximum = arr[low];
      for (int i=low+1; i<=high; i++)
      if (maximum < arr[i])
         maximum = arr[i];
      return maximum;
   }
int minimum_removals(int arr[], int low, int high)
   {
      if (low >= high)
      return 0;
      int m1 = min(arr, low, high);
      int m2 = max(arr, low, high);
      if (2*m1 > m2)
      return 0;
      return min(minimum_removals(arr, low+1, high), minimum_removals(arr, low, high-1)) + 1;
   }
int main()
   {
      int arr[] = {12, 45, 32, 88, 100};
      int n = sizeof(arr)/sizeof(arr[0]);
      cout << minimum_removals(arr, 0, n-1);
      return 0;
   }

Ausgabe

3

Fazit

Hier verwenden wir die Brute-Force-Methode, um das längste Subarray zu finden. Andere mögliche Lösungen könnten darin bestehen, jedes mögliche Subarray durch wiederholtes Herausnehmen von Elementen von beiden Seiten und andere Methoden zu überprüfen. Dennoch ist ihre Umsetzung arbeitsintensiv und wenig optimiert. Die zeitliche Komplexität beträgt hier O(n^2), da wir bereits alle Unterarrays durchlaufen haben.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Entfernen des kleinsten Elements auf beiden Seiten, sodass der 2*-Mindestwert größer als der Maximalwert ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!