Susun semula tatasusunan supaya jumlah hasil pasangan unsur berturut-turut adalah minimum, ditulis dalam C++

Kami mempunyai susunan jenis integer positif, dengan mengandaikan ia adalah arr[], dengan sebarang saiz. Tugasnya adalah untuk menyusun semula tatasusunan supaya apabila kita mendarab unsur dengan unsur bersebelahan dan kemudian menambah semua elemen yang terhasil, jumlah terkecil dikembalikan.

Mari kita lihat situasi input dan output yang berbeza:

Input - int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}

Output - Menyusun semula tatasusunan hasil tambah, iaitu hasil darab pasangan unsur berturut-turut ialah: 7 0 5 0 5 1 2 1

Penjelasan- Kami mempunyai tatasusunan integer bersaiz 8. Sekarang kita akan menyusun semula tatasusunan iaitu 7 0 5 0 5 1 2 1. Kami akan menyemak sama ada jumlah minimum dikembalikan, iaitu 7 * 0 + 5 * 0 + 5 * 1 + 2 * 1 = 0 + 0 + 5 + 2 = 7.

Input - int arr[] = {1, 3, 7, 2, 4, 3}

Output - Susun semula tatasusunan untuk meminimumkan jumlah, iaitu hasil darab pasangan unsur berturut-turut ialah : 7 1 4 2 3 3

Penjelasan- Kami mempunyai susunan integer bersaiz 6. Sekarang kita akan menyusun semula tatasusunan iaitu 7 1 4 2 3 3. Kami akan menyemak sama ada jumlah minimum dikembalikan, iaitu 7 * 1 + 4 * 2 + 3 * 3 = 7 + 8 + 9 = 24.

Kaedah yang digunakan dalam atur cara di bawah adalah seperti berikut:

• Masukkan tatasusunan jenis integer dan kira saiz tatasusunan.

• Isih tatasusunan menggunakan kaedah isihan C++ STL, menghantar tatasusunan dan saiz tatasusunan kepada fungsi isih.

• Isytihar pembolehubah integer dan tetapkannya sebagai nilai pulangan bagi fungsi panggilan.

Rearrange_min_sum(arr, size)

Di dalam fungsi Rearrange_min_sum(arr, size)

• Buat pembolehubah, katakan, jenis vektor jenis 'genap' dan 'ganjil' yang menyimpan pembolehubah integer

• . Isytiharkan pembolehubah sebagai temp dan jumlah dan mulakan dengan 0.

• Mulakan gelung FOR daripada i ke 0 sehingga i kurang daripada saiz Di dalam gelung, periksa JIKA i kurang daripada saiz/2 kemudian tolak arr[i] ke vektor ganjil ELSE, tolak arr[i] kepada vektor genap

• Panggil kaedah isihan dengan menghantar genap.mula(), genap.akhir() dan lebih besar().

• Mulakan gelung UNTUK dari i kepada 0 sehingga i kurang daripada genap.size(). Di dalam gelung, tetapkan arr[temp++] kepada genap[j], arr[temp++] kepada ganjil[j] dan jumlah kepada jumlah + genap[j] * ganjil[j]

• Jumlah pulangan

Cetak hasilnya.

Contoh

#include <bits/stdc++.h>
using namespace std;
int Rearrange_min_sum(int arr[], int size){
   vector<int> even, odd;
   int temp = 0;
   int total = 0;
   for(int i = 0; i < size; i++){
      if (i < size/2){
         odd.push_back(arr[i]);
      }
      else{
         even.push_back(arr[i]);
      }
   }
   sort(even.begin(), even.end(), greater<int>());
   for(int j = 0; j < even.size(); j++){
      arr[temp++] = even[j];
      arr[temp++] = odd[j];
      total += even[j] * odd[j];
   }
   return total;
}
int main(){
   int arr[] = { 2, 5, 1, 7, 5, 0, 1, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   //sort an array
   sort(arr, arr + size);
   //call function
   int total = Rearrange_min_sum(arr, size);
   cout<<"Rearrangement of an array to minimize sum i.e. "<<total<<" of product of consecutive pair elements is: ";
   for(int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

Output

, Jika kita akan menjana kod berikut di atas

Atas ialah kandungan terperinci Susun semula tatasusunan supaya jumlah hasil pasangan unsur berturut-turut adalah minimum, ditulis dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!