資料結構
網路
關係資料庫管理系統
作業系統
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.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/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 次檢視
