Program C++ untuk mengeluarkan elemen terkecil dari kedua-dua belah supaya nilai 2*minimum lebih besar daripada nilai maksimum

Masalahnya melibatkan pengalihan keluar elemen dari kedua-dua belah senarai integer dengan cara yang 2*min lebih besar daripada maks .

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

Kita boleh menggunakan kaedah brute force. Kami boleh mencuba semua kemungkinan kepuasan dan mencari subarray terpanjang yang memenuhi syarat 2*min > maks. Kami juga boleh menggunakan kaedah pengaturcaraan dinamik untuk mencuba semua kemungkinan kombinasi subarray yang berlebihan dan tidak diingini.

Contoh (menggunakan vektor ADT)

Andaikan kita mempunyai tatasusunan, seperti "[250, 10, 11, 12, 19, 200]". Untuk mendapatkan penyelesaian terbaik kita perlu mengalih keluar elemen [250, 200] untuk membentuk tatasusunan [10, 11, 12, 19] di mana min ialah 10 dan maks ialah 19. Oleh itu 2*10 > 19. Kami mencetak daripada tatasusunan, jadi outputnya ialah 2.

Di bawah ialah program C++ yang menerangkan cara mengalih keluar bilangan minimum elemen daripada tatasusunan supaya dua kali nilai minimum lebih besar daripada nilai maksimum -

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

Output

2

Contoh (tanpa vektor ADT)

Berikut ialah program C++ yang menerangkan cara mengalih keluar bilangan minimum elemen daripada tatasusunan supaya dua kali nilai minimum lebih besar daripada nilai maksimum, tetapi tanpa menggunakan 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;
   }

Output

3

Kesimpulan

Di sini kami menggunakan kaedah brute force untuk mencari subarray terpanjang. Penyelesaian lain yang mungkin termasuk menyemak setiap subarray yang mungkin dengan berulang kali muncul elemen dari kedua-dua belah pihak dan kaedah lain. Walau bagaimanapun, pelaksanaannya adalah intensif buruh dan kurang dioptimumkan. Kerumitan masa di sini ialah O(n^2) kerana kami telah mengulangi semua sub-tatasusunan.

Atas ialah kandungan terperinci Program C++ untuk mengeluarkan elemen terkecil dari kedua-dua belah supaya nilai 2*minimum lebih besar daripada nilai maksimum. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!