贪心思想,每次都选最轻的两堆
采用优先队列实现。
#include <iostream> using namespace std; int n; const int maxn = 10010; int arr[maxn]; int total = 0; void push(int x) { total++; arr[total] = x; int j = total; int i = j / 2; while (i > 0 && arr[j] < arr[i]) { swap(arr[i], arr[j]); j = i; i = j / 2; } } int top() { return arr[1]; } void pop() { arr[1] = arr[total]; total--; int i = 1; int j = i * 2; if (j + 1 <= total && arr[j + 1] < arr[j])j = j + 1; while (j <=total&&arr[j]<arr[i]) { swap(arr[i], arr[j]); i = j; j = i * 2; if (j + 1 <= total && arr[j + 1] < arr[j])j = j + 1; } } int main() { cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; push(x); } int ans = 0; for (int i = 1; i < n; i++) { int x = top(); pop(); int y = top(); pop(); ans += x + y; push(x + y); } cout << ans; }