小根堆的写法太复杂记不住,用的默认的大根堆方式,重载小于号时需注意逻辑关系
#include <iostream> #include "queue" using namespace std; struct myInt { int data; bool operator< (myInt m)const { return data > m.data;//数值大的优先级低 } myInt(int a) { data = a; } }; int main() { int n; while (cin >> n) { // 注意 while 处理多个 case // cout << a + b << endl; priority_queue<myInt> myQueue; while (n--) { int temp; cin >> temp; myQueue.push(myInt(temp)); } int ans = 0; while (myQueue.size()>1) {//相加到根结点停止 int a = myQueue.top().data; myQueue.pop(); int b = myQueue.top().data; myQueue.pop(); ans += a + b; myQueue.push(myInt(a + b)); } cout<<ans<<endl; } } // 64 位输出请用 printf("%lld")