C++ program: Count the number of operations required to make all gifts equal in quantity

Suppose we have two arrays A and B, each of size n. There are n gifts and we want to give them to some children. The i-th gift consists of A[i] candies and B[i] oranges. During a move, we can select some gifts and perform one of the following actions -

• Take a candy from that gift (if any); p>

• Take out an orange from this gift (if there is one);

• Take out a candy and an orange gift from this gift (if there is one) if).

All gifts should be created equal. This means that after a series of moves, the following two The conditions should be met: A[0] = A[1] = ... = A[n-1] and B[0] = B[1] = ... = B[n-1]. we have to Find the minimum number of steps required to make all given gifts equal.

Problem Category

The above problems can be solved by applying greedy problem solving techniques. Greedy algorithm technology is the type of algorithm that currently provides the best solution Choose rather than try all possible solutions. Greedy algorithm technology also Used to solve optimization problems, just like its big brother dynamic programming. Active When programming, you need to traverse all possible sub-problems and find the optimal one solution, but it has a drawback; it requires more time and space. Therefore, in various Scenario greedy technique is used to find the best solution to the problem. Although it is true does not give the best solution in all situations, if designed carefully it can produce a solution faster than Dynamic programming problem. Greedy techniques provide local optimal solutions Optimization. Examples of this technique include Kruskal and Prim's minimal Spanning tree (MST) algorithm, Huffman tree coding, Dijkstra's single source shortest path Questions etc

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

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

So, if the input to our problem is A = [3, 5, 6]; B = [3, 2, 3], then the output is 6, Since it was originally taken from B, now B[0] becomes [2, 2, 3], and then taken from A[1], so A = [3, 4, 6], then again from A[1], so A = [3, 3, 6], then from A[2] and B[2], so they to [3, 3, 5] and [2, 2, 2], then from A[2] to A = [3, 3, 4], again from A[2] to Let it be [3, 3, 3]. So now A has the same number of candies and B has the same number of oranges.

Steps

To solve this problem we will follow the following steps-

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

Example

Let us see the following implementation for better understanding -

#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

The above is the detailed content of C++ program: Count the number of operations required to make all gifts equal in quantity. For more information, please follow other related articles on the PHP Chinese website!