数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：计算使所有礼物数量相同的操作次数
假设我们有两个数组A和B，每个数组的大小为n。有n份礼物，我们想把它们送给一些孩子。第i份礼物有A[i]颗糖果和B[i]个橙子。在一次移动中，我们可以选择一些礼物并执行以下操作之一：
从这份礼物中取出恰好一颗糖果（如果可用）；
从这份礼物中取出恰好一个橙子（如果可用）；
从这份礼物中取出恰好一颗糖果和恰好一个橙子（如果可用）。
所有礼物都应该相等。这意味着在执行一系列移动后，以下两个条件应该满足：A[0] = A[1] = ... = A[n-1] 且 B[0] = B[1] = ... = B[n-1]。我们必须找到使所有礼物都相等所需的最小移动次数。
问题类别
上述问题可以通过应用贪心问题解决技术来解决。贪心算法技术是一种算法类型，其中选择当前最佳解决方案，而不是遍历所有可能的解决方案。贪心算法技术也用于解决优化问题，就像它更大的兄弟动态规划一样。在动态规划中，有必要遍历所有可能的子问题以找出最优解，但它有一个缺点；它需要更多的时间和空间。因此，在各种情况下，使用贪心技术来找到问题的最优解。虽然它并非在所有情况下都能提供最优解，但如果设计得当，它可以比动态规划问题更快地产生解决方案。贪心技术为优化问题提供局部最优解。此技术的示例包括克鲁斯卡尔和普里姆的最小生成树 (MST) 算法、霍夫曼树编码、迪杰斯特拉的单源最短路径问题等。
https://tutorialspoint.com/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm
因此，如果我们问题的输入类似于 A = [3, 5, 6]；B = [3, 2, 3]，则输出将为 6，因为最初从 B 中取出，所以现在 B[0] 变为 [2, 2, 3]，然后从 A[1] 中取出，所以 A = [3, 4, 6]，然后再次从 A[1] 中取出，所以 A = [3, 3, 6]，然后从 A[2] 和 B[2] 中取出，所以它们变为 [3, 3, 5] 和 [2, 2, 2]，然后从 A[2] 中取出，所以它变为 A = [3, 3, 4]，然后再次从 A[2] 中取出以使其变为 [3, 3, 3]。所以现在 A 具有相同数量的糖果，而 B 具有相同数量的橙子。
步骤
为了解决这个问题，我们将遵循以下步骤：
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
示例
让我们看看以下实现以获得更好的理解：
#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;
}输入
{ 3, 5, 6 }, { 3, 2, 3 }输出
6
1K+ 次查看
