优先队列 POJ 3253 Fence Repair
2024-08-30 16:14:15
题意:一块木板按照某个顺序切成a[1], a[2]...a[n]的长度,每次切都会加上该两段木板的长度,问选择什么顺序切能使得累加和最小
分析:网上说这是哈夫曼树。很容易想到先切掉最长的,反过来也就是相当于每次取最短的两块合并成一块,直到最后剩下原来的一块,优先队列实现
代码:
/************************************************
* Author :Running_Time
* Created Time :2015/9/14 星期一 08:51:15
* File Name :POJ_3253.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 2e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int a[N]; int main(void) {
int n;
while (scanf ("%d", &n) == 1) {
for (int i=1; i<=n; ++i) scanf ("%d", &a[i]);
priority_queue<int, vector<int>, greater<int> > Q;
for (int i=1; i<=n; ++i) Q.push (a[i]);
ll ans = 0;
while (Q.size () > 1) {
int l1 = Q.top (); Q.pop ();
int l2 = Q.top (); Q.pop ();
ans += l1 + l2;
Q.push (l1 + l2);
}
printf ("%I64d\n", ans);
} return 0;
}
最新文章
- NV显卡Ubuntu14.04更新软件导致登录死循环,不过可以进入tty模式
- tomcat manager配置
- C#面向对象编程进阶(一) ——实现栈
- css默认样式
- declare 关键字在Oracle中的应用。
- jquery技巧总结
- HDU 3518 Boring counting(后缀数组,字符处理)
- 实现LoadRunner多个场景的顺序执行
- 认识HTML5
- atomikos的Jta配置
- 震荡信号Simulink仿真
- JQuery树形目录插件Dynatree
- C语言博客作业—结构体
- Python 3 re模块3个括号相关的语法
- 001-zookeeper 简介-paxos算法,zk简介,特点
- 记一个神奇的Bug
- 调用Bytom Chrome插件钱包开发Dapp
- 关于WebService
- error2019-01-17 宏STDOUT_FILENO
- python 正则表达式 group() groups()