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

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

PHPz
Lepaskan: 2023-08-28 08:09:14
ke hadapan
1298 orang telah melayarinya

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 .

1

2

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

res = solve(arr);

Salin selepas log masuk

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 -

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

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

}

Salin selepas log masuk

Output

1

2

Salin selepas log masuk

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 -

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

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

   }

Salin selepas log masuk

Output

1

3

Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan