C++ 程序获得拼图块之间的最小差异

假设我们有一个包含 m 个元素和另一个数字 n 的数组 A。阿迈勒决定给他的 n 个朋友一份礼物，所以他会给他们每人一个拼图游戏。店员告诉他，店里有m个拼图，但难度和大小可能有所不同。具体来说，第 i 个拼图游戏由 A[i] 块组成。因此，阿迈勒决定，他的礼物中的件数之间的差异必须尽可能小。设 x 为他购买的最大拼图中的碎片数，y 为最小的拼图中的碎片数。他想要选择这样的 n 个谜题，使得 x - y 尽可能最小。我们必须找到 x - y 的最小可能值。

问题类别

上述问题可以通过应用贪心问题解决技术来解决。 贪婪算法技术是当前最佳解决方案是的算法类型 选择而不是尝试所有可能的解决方案。贪心算法技术也 用于解决优化问题，就像它的大哥动态规划一样。动态中 编程时，需要遍历所有可能的子问题，找出最优的 解决方案，但它有一个缺点；这需要更多的时间和空间。所以，在各种 场景贪婪技术用于找出问题的最佳解决方案。虽然确实如此 并不是在所有情况下都能给出最佳解决方案，如果精心设计，它可以比以下更快地产生解决方案 动态规划问题。贪心技术提供了局部最优解 优化问题。这种技术的例子包括 Kruskal 和 Prim 的最小 生成树（MST）算法、霍夫曼树编码、Dijkstra 的单源最短路径 问题等

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

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

所以，如果我们问题的输入是这样的 A = [10, 12, 10, 7, 5, 22]; n = 4.，则输出将为 5， 因为有4个朋友。这家商店出售 6 个拼图。如果阿迈勒买了前四个拼图 分别由 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