编程算法 - 篱笆修理(Fence Repair) 堆(heap) 代码(C++)
篱笆修理(Fence Repair) 堆(heap) 代码(C++)
本文地址: http://blog.csdn.net/caroline_wendy
题目参考: http://blog.csdn.net/caroline_wendy/article/details/37911157
本题比较简单, 直接使用堆(heap)选取两个最小的值, 合并再放入堆, 最后求出和.
【编程算法 - 篱笆修理(Fence Repair) 堆(heap) 代码(C++)】比起贪婪算法O(n^2), 时间复杂度O(nlogn).
代码:
/*
* main.cpp
*
*Created on: 2014.7.20
*Author: spike
*//*eclipse cdt, gcc 4.8.1*/#include #include
#include
#include using namespace std;
class Program {
static const int MAX_N = 100;
int N=3, L[MAX_N] = {8,5,8};
public:
void solve() {
int ans = 0;
priority_queue, greater> que;
for (int i=0;
i 1) {
int l1, l2;
l1 = que.top();
que.pop();
l2 = que.top();
que.pop();
ans += l1+l2;
que.push(l1+l2);
}
printf("result = %d\n", ans);
}
};
int main(void)
{
Program iP;
iP.solve();
return 0;
} 输出:
result = 34
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- python青少年编程比赛_第十一届蓝桥杯大赛青少年创意编程组比赛细则
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- HTML基础--基本概念--跟着李南江学编程
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 我的软件测试开发工程师书单