Program C++: Kira bilangan operasi yang diperlukan untuk menjadikan semua hadiah sama dalam kuantiti

Katakan kita mempunyai dua tatasusunan A dan B, setiap satu bersaiz n. Terdapat n hadiah dan kami ingin memberikannya kepada beberapa kanak-kanak. Hadiah ke-i terdiri daripada gula-gula A[i] dan oren B[i]. Semasa bergerak, kita boleh memilih beberapa hadiah dan melakukan salah satu daripada tindakan berikut -

• keluarkan gula-gula daripada hadiah ini (jika ada); p>

• Keluarkan satu gula-gula dan satu hadiah oren daripada hadiah ini (jika ada).

• Semua hadiah harus dicipta sama rata. Ini bermakna selepas beberapa siri pergerakan, dua yang berikut Syarat harus dipenuhi: A[0] = A[1] = ... = A[n-1] dan B[0] = B[1] = ... = B[n-1]. kita terpaksa Cari bilangan langkah minimum yang diperlukan untuk menjadikan semua hadiah yang diberikan sama.

Kategori Masalah

Masalah di atas boleh diselesaikan dengan mengaplikasikan teknik penyelesaian masalah tamak. Teknologi algoritma tamak ialah jenis algoritma yang pada masa ini menyediakan penyelesaian terbaik Pilih daripada mencuba semua penyelesaian yang mungkin. Teknologi algoritma tamak juga Digunakan untuk menyelesaikan masalah pengoptimuman, sama seperti pengaturcaraan dinamik abangnya. Aktif Apabila pengaturcaraan, anda perlu merentasi semua sub-masalah yang mungkin dan mencari yang optimum penyelesaian, tetapi ia mempunyai kelemahan; ia memerlukan lebih banyak masa dan ruang. Oleh itu, dalam pelbagai Teknik tamak senario digunakan untuk mencari penyelesaian terbaik kepada masalah tersebut. Walaupun ianya benar tidak memberikan penyelesaian terbaik dalam semua situasi, jika direka dengan teliti ia boleh menghasilkan penyelesaian lebih cepat daripada Masalah pengaturcaraan dinamik. Teknik tamak menyediakan penyelesaian optimum tempatan masalah pengoptimuman. Contoh teknik ini termasuk Kruskal dan Prim's minimum Algoritma spanning tree (MST), pengekodan pokok Huffman, laluan terpendek sumber tunggal Dijkstra Soalan dan lain-lain

https://www.tutorialspoint.com/data_structurals_algorithms/greedy_algorithms.htm

https://www.tutorialspoint.com/data_structurals_algorithms/dynamic_programming.htm

Jadi, jika input ini adalah masalah kita = [3, 5, 6]; B = [3, 2, 3], maka keluarannya ialah 6, Oleh kerana ia pada asalnya diambil daripada B, kini B[0] menjadi [2, 2, 3], dan kemudian diambil daripada A[1], jadi A = [3, 4, 6], kemudian sekali lagi dari A[1], jadi A = [3, 3, 6], kemudian dari A[2] dan B[2], jadi mereka kepada [3, 3, 5] dan [2, 2, 2], kemudian dari A[2] ke A = [3, 3, 4], sekali lagi dari A[2] ke Biarlah [3, 3, 3]. Jadi sekarang A mempunyai bilangan gula-gula yang sama dan B mempunyai bilangan oren yang sama.

Langkah p>

Untuk menyelesaikan masalah ini kami akan mengikuti langkah berikut -

minA := inf
minB := inf
kq := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   minA := minimum of minA and A[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   minB := minimum of minB and B[i]
for initialize i := 0, when i < n, update (increase i by 1), do:
   kq := kq + maximum of (A[i] - minA) and (B[i] - minB)
return kq

Contoh

Mari kita lihat pelaksanaan berikut untuk pemahaman yang lebih baik -

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, vector<int> B){
   int minA = 999, minB = 999, kq = 0;
   int n = A.size();
   for (int i = 0; i < n; i++)
      minA = min(minA, A[i]);
   for (int i = 0; i < n; i++)
      minB = min(minB, B[i]);
   for (int i = 0; i < n; i++)
      kq += max(A[i] - minA, B[i] - minB);
   return kq;
}
int main(){
   vector<int> A = { 3, 5, 6 };
   vector<int> B = { 3, 2, 3 };
   cout << solve(A, B) << endl;
}

Input

{ 3, 5, 6 }, { 3, 2, 3 }

Output

6

Atas ialah kandungan terperinci Program C++: Kira bilangan operasi yang diperlukan untuk menjadikan semua hadiah sama dalam kuantiti. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!