- 【原理】 貪心法則是一種符合人類直覺的抽象思維，每一步只考慮目前的最佳選擇，且之前的選擇不會影響後面的選擇。不斷的選擇局部的最佳解，全部執行結束後就會獲得整體的最佳解。
- 【貪心不成立】若可以舉出反例，就證明所使用的貪婪演算法中的貪婪準則是不正確的。
- 【經典題型】物品可分割的背包問題
- 【經典題型】排程問題：ZeroJudge a567: 死線排程 【題解】
- 【範例】ZeroJudge d221: 10954 – Add All 【題解】
- 因為加法的代價會不斷累計，因此不斷地從最小的數字先相加，代價最低。
- 利用priority_queue，但排序由小到大。取出最小的兩個數字，相加後放回priority_queue，重新排序。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n, num, a, b;
while (cin >> n){
if (n == 0) break;
priority_queue <int, vector<int>, greater<int>> pq;
long long count = 0;
for (int i = 0; i < n; i++){
cin >> num;
pq.push(num);
}
for (int i = 0; i < n-1; i++){
a = pq.top();
pq.pop();
b = pq.top();
pq.pop();
count += a+b;
pq.push(a+b);
}
cout << count << endl;
}
}
Post Views (since April 2021) : 4,055