A18787. 简易石子合并
填空题
较难
知识点
题目描述
简易石子合并
题目描述
给定n堆石子，每次合并任意两堆，合并代价为两堆石子重量之和，求将所有石子合并为一堆的最小总代价。
输入格式
第一行整数n；第二行n个整数表示每堆石子重量。
输出格式
输出最小总代价。
数据范围 1≤n≤100
参考答案
#include <iostream>
#include <queue>
using namespace std;
int main()
{
// 小根堆定义，动态取出最小值
priority_queue<int, vector<int>, greater<int>> heap;
int n, x;
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> x;
heap.push(x);
}
long long total = 0; // 防止数据溢出，必须用long long
while(heap.size() > 1)
{
int a = heap.top(); heap.pop(); // 取最小第一堆
int b = heap.top(); heap.pop(); // 取最小第二堆
int sum = a + b;
total += sum; // 累加合并代价
heap.push(sum); // 新堆入队
}
cout << total;
return 0;
}答案解析
1. 算法类型：优先队列（小根堆）贪心，哈夫曼树经典应用；
2. 贪心规则：每次取出重量最小的两堆合并，累加代价，新堆重新入堆；
3. 关键细节：总代价要用long long，防止整数溢出；必须用小根堆，大根堆答案完全错误；
4. 终止条件：堆中仅剩1堆时停止合并。
评分细则
正确定义小根堆（4分，大根堆直接0分）、循环合并逻辑正确（3分）、long long防溢出（2分）、输入输出正确（1分）
上一题
下一题