一个很长的英文背景,其他不说了,就是告诉你锯一个长度为多少的木板就要花多少的零钱,把一块足够长(不是无限长)的木板锯成n段,每段长度都告诉你了,让你求最小花费。
明显的huffman树,优先队列是个很好的东西。
#include <stdio.h> #include <queue> #include <algorithm> #include <iostream> #include <vector> #define ll __int64 using namespace std; int n; struct cmp //优先级重载 { bool operator()(ll x, ll y) { return x > y; } }; priority_queue<ll, vector<ll>, cmp> q; int main() { ll x; while (scanf("%d", &n) != EOF) { while (!q.empty()) q.pop(); ll sum = 0; for (int i = 1; i <= n; i++) { cin >> x; sum += x; q.push(x); } ll ans = 0; // while (!q.empty()) {printf("%d ", q.top()); q.pop();} while (!q.empty()) { ll a = q.top(); q.pop(); ll b = q.top(); q.pop(); ans += a+b; x = a+b; if (!q.empty()) q.push(x); } cout << ans << endl; } return 0; }