資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：尋找糖果分配的最小k值
假設我們有一個包含n個元素的陣列A。Amal有n個朋友，他的第i個朋友有A[i]顆糖果。Amal的朋友們不喜歡他們擁有不同數量的糖果。因此，Amal執行以下操作集恰好一次：
Amal選擇k (0 ≤ k ≤n)個任意朋友
Amal將他們的A[i1] + A[i2] + ... + A[ik]顆糖果分配給所有n個朋友。在分配過程中，對於每顆A[i1] + A[i2] + ... + A[ik]糖果，他都會選擇新的擁有者。這可以是任何n個朋友中的一個。（任何糖果都可以給予在分配過程之前擁有該糖果的人）。
並且，k值並非預先固定，可以是任意的。我們需要找到k的最小值。
問題類別
上述問題可以透過應用貪心演算法解決。貪心演算法是一種選擇當前最佳解而不是遍歷所有可能解的演算法。貪心演算法也用於解決最佳化問題，就像它的“兄長”動態規劃一樣。在動態規劃中，需要遍歷所有可能的子問題才能找到最優解，但這有一個缺點：它需要更多的時間和空間。因此，在各種情況下，貪心演算法被用來找到問題的最優解。雖然它並非在所有情況下都能給出最優解，但如果設計得當，它可以比動態規劃更快地產生解。貪心演算法為最佳化問題提供區域性最優解。這種技術的例子包括克魯斯卡爾和普里姆最小生成樹 (MST) 演算法、霍夫曼樹編碼、迪傑斯特拉單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入類似於A = [4, 5, 2, 5]，則輸出將為2。
步驟
為了解決這個問題，我們將遵循以下步驟：
sum := 0 ans := 0 n := size of A for initialize i := 0, when i < n, update (increase i by 1), do: sum := sum + A[i] if sum mod n is not equal to 0, then: return -1 Otherwise sum := sum / n for initialize i := 0, when i < n, update (increase i by 1), do: if A[i] > sum, then: (increase ans by 1) return ans
示例
讓我們看看下面的實現來更好地理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n, sum = 0, ans = 0;
n = A.size();
for (int i = 0; i < n; i++)
sum += A[i];
if (sum % n != 0)
return -1;
else{
sum /= n;
for (int i = 0; i < n; i++)
if (A[i] > sum)
ans++;
return ans;
}
}
int main(){
vector<int> A = { 4, 5, 2, 5 };
cout << solve(A) << endl;
}輸入
{ 4, 5, 2, 5 }輸出
2
284 次瀏覽
