数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序找出最强和最弱之间的最小差值
假设我们有一个包含n个元素的数组A。一场比赛中有n名运动员。他们的编号从1到n，并按从左到右的顺序排列。每个运动员i的力量是A[i]。我们希望将所有运动员分成两队。每个队至少必须有一名运动员，并且每个运动员必须且只能在一个队中。我们希望第一队的最强运动员与第二队的最弱运动员的差异尽可能小。我们必须找到上面提到的他们力量之间的最小差值。
问题类别
上述问题可以通过应用贪心问题解决技术来解决。贪心算法技术是一种算法，其中选择当前最佳解决方案，而不是遍历所有可能的解决方案。贪心算法技术也用于解决优化问题，就像它的“大哥”动态规划一样。在动态规划中，有必要遍历所有可能的子问题以找出最优解，但它有一个缺点；即它需要更多的时间和空间。因此，在各种情况下，使用贪心技术来找出问题的最优解。虽然它并非在所有情况下都能提供最优解，但如果设计得当，它可以比动态规划问题更快地产生解决方案。贪心技术为优化问题提供局部最优解。此技术的示例包括克鲁斯卡尔和普里姆的最小生成树 (MST) 算法、霍夫曼树编码、迪杰斯特拉的单源最短路径问题等。
https://tutorialspoint.com/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.com/data_structures_algorithms/dynamic_programming.htm
因此，如果我们问题的输入类似于 A = [2, 1, 3, 2, 4, 3]，则输出将为 0，因为其中一个最佳拆分是 T1 = [2, 1] 和 T2 = [3, 2, 4, 3]，所以 |2 - 2| = 0。
步骤
为了解决这个问题，我们将遵循以下步骤 -
n := size of A sort the array A ans := 1000 for initialize i := 1, when i < n, update (increase i by 1), do: ans := minimum of ans and A[i] - A[i - 1] return ans
示例
让我们看看以下实现以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
sort(A.begin(), A.end());
int ans = 1000;
for (int i = 1; i < n; ++i){
ans = min(ans, A[i] - A[i - 1]);
}
return ans;
}
int main(){
vector<int> A = { 2, 1, 3, 2, 4, 3 };
cout << solve(A) << endl;
}输入
{ 2, 1, 3, 2, 4, 3 }输出
0
135 次查看
