数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++程序：获取拼图碎片之间最小差值
假设我们有一个包含m个元素的数组A和另一个数字n。Amal决定给他n个朋友送礼物，所以他会给每人一个拼图。店员告诉他店里有m个拼图，但它们的难度和尺寸可能不同。具体来说，第i个拼图包含A[i]块。所以Amal决定他礼物中拼图块数的差值必须尽可能小。设x是他购买的最大拼图的块数，y是最小拼图的块数。他希望选择n个拼图，使x - y尽可能小。我们必须找到x - y的最小可能值。
问题类别
上述问题可以通过应用贪心算法解决。贪心算法是一种选择当前最佳解决方案而不是遍历所有可能解决方案的算法。贪心算法也用于解决优化问题，就像它的“大哥”动态规划一样。在动态规划中，需要遍历所有可能的子问题才能找到最优解，但这有一个缺点：它需要更多的时间和空间。因此，在各种情况下，贪心算法被用来找到问题的最优解。虽然它并非在所有情况下都能提供最优解，但如果设计仔细，它可以比动态规划更快地产生解。贪心算法为优化问题提供局部最优解。这种技术的例子包括克鲁斯卡尔和普里姆最小生成树(MST)算法、霍夫曼树编码、迪杰斯特拉单源最短路径问题等。
https://tutorialspoint.com/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm
因此，如果我们问题的输入类似于A = [10, 12, 10, 7, 5, 22]；n = 4，那么输出将是5，因为有4个朋友。商店出售6个拼图。如果Amal购买前四个拼图，分别包含10、12、10和7块，那么最大和最小拼图尺寸之间的差值为5。不可能得到更小的差值。
步骤
为了解决这个问题，我们将遵循以下步骤：
ans := 1000 m := size of A sort the array A for initialize i := n - 1, when i < m, update (increase i by 1), do: ans := minimum of ans and (A[i] - A[i - (n - 1)]) return ans
示例
让我们看看下面的实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, double n){
int ans = 1000;
int m = A.size();
sort(A.begin(), A.end());
for (int i = n - 1; i < m; i++)
ans = min(ans, A[i] - A[i - (n - 1)]);
return ans;
}
int main(){
vector<int> A = { 10, 12, 10, 7, 5, 22 };
double n = 4.;
cout << solve(A, n) << endl;
}输入
{ 10, 12, 10, 7, 5, 22 }, 4输出
5
224 次浏览
