C++程序，从两侧删除最小的元素，使得2*最小值大于最大值-C++-PHP中文网

c++程序，从两侧删除最小的元素，使得2*最小值大于最大值

该问题涉及以 2*min 大于 max 的方式从整数列表的任意一侧删除元素。

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

我们可以使用暴力方法。我们可以尝试所有可能的满足并找到满足 2*min > max 条件的最长子数组。我们还可以使用动态规划方法来尝试所有可能的过度且不需要的子数组组合。

示例（使用矢量 ADT）

假设我们有一个数组，例如“[250, 10, 11, 12, 19, 200]”。为了获得最佳解决方案，我们需要删除元素 [250, 200] 以形成数组 [10, 11, 12, 19]，其中 min 为 10，max 为 19。因此 2*10 > 19。我们从数组，因此输出打印为 2。

下面是一个 C++ 程序，它描述了如何从数组中删除最小数量的元素，使得最小值的两倍大于最大值 -

Endel.io

Endel是一款可以创造个性化舒缓声音的应用程序，可帮助您集中注意力、放松身心和入睡。

下载

立即学习“C++免费学习笔记（深入）”；

#include 
#include 
using namespace std;
int solve(vector arr) {
   int startIndex = 0, endIndex = 0;
   bool foundAnAnswer = false;
   for (int start=0; start 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 arr = {250, 10, 11, 12, 19, 200};
   cout << solve(arr);
   return 0;
}

输出

示例（不使用矢量 ADT）

下面是一个 C++ 程序，描述如何从数组中删除最小数量的元素，使得最小值的两倍大于最大值，但不使用 Vector ADT -

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