Poj3253 Fence Repair (优先队列)

时间:2021-10-30 07:27:29
Fence Repair
Time Limit: 2000MS   Memory Limit: 65536K
Total Submissions: 67319   Accepted: 22142

Description

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.

FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.

Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.

Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

Input

Line 1: One integer N, the number of planks 
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank

Output

Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts

Sample Input

3
8
5
8

Sample Output

34

Hint

He wants to cut a board of length 21 into pieces of lengths 8, 5, and 8. 
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).
 
要用long long类型
 #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
int main()
{
ll n,x;
while(cin>>n){
priority_queue<int,vector<int>,greater<int> > pq;
while(n--){
cin>>x;
pq.push(x);
}
ll sum=;
while(pq.size()>){
ll x1=pq.top();
pq.pop();
ll x2=pq.top();
pq.pop();
sum+=x1+x2;
pq.push(x1+x2);
}
cout<<sum<<endl;
}
return ;
}

Poj3253 Fence Repair (优先队列)的更多相关文章

  1. poj 3253 Fence Repair 优先队列

    poj 3253 Fence Repair 优先队列 Description Farmer John wants to repair a small length of the fence aroun ...

  2. 优先队列 poj3253 Fence Repair

    Fence Repair Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 51411   Accepted: 16879 De ...

  3. POJ - 3253 Fence Repair 优先队列&plus;贪心

    Fence Repair Farmer John wants to repair a small length of the fence around the pasture. He measures ...

  4. POJ Fence Repair&lpar;优先队列)

    Fence Repair Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 51346   Accepted: 16857 De ...

  5. poj3253 Fence Repair【哈夫曼树&plus;优先队列】

    Description Farmer John wants to repair a small length of the fence around the pasture. He measures ...

  6. poj-3253 fence repair(贪心题)

    题目描述: Farmer John wants to repair a small length of the fence around the pasture. He measures the fe ...

  7. poj3253 Fence Repair

    http://poj.org/problem?id=3253 Farmer John wants to repair a small length of the fence around the pa ...

  8. POJ3253 Fence Repair&lpar;贪心&rpar;

    分割木板的顺序是*的,所以每次选择两块最短的板,组合在一起,增加队列,原来两个板出队,直到队列中为空或者仅仅剩下一个板时结束.这里使用优先队列较为方便. #include<iostream&g ...

  9. poj 3053 Fence Repair&lpar;优先队列&rpar;

    题目链接:http://poj.org/problem?id=3253 思路分析:题目与哈夫曼编码原理相同,使用优先队列与贪心思想:读入数据在优先队列中,弹出两个数计算它们的和,再压入队列中: 代码如 ...

随机推荐

  1. php、前端开发(网站建设)环境搭建

    php集成开发环境wampserver,是一款免费开源的软件,下载地址http://www.wampserver.com,由于是国外的网站,打开速度慢,根据自己的电脑选择32位/64位的系统下载.

  2. 手动删除portal中托管服务。

    在portal中将server作为托管联合服务器,然后发布了托管服务.若中间取消了托管联合服务器,再重新连接,那么会出现之前的托管服务无法删除的现象. 下文为怎样手动删除这些服务的方法,(不过貌似之后 ...

  3. C语言复习

  4. jQuery学习笔记----入门

    基础语法是:$(selector).action() 美元符号定义 jQuery 选择符(selector)“查询”和“查找” HTML 元素 jQuery 的 action() 执行对元素的操作

  5. centos 网站目录权限参考

    Linux下Apache网站目录读写权限的设置 网站目录文件权限的设置对网站的安全至关重要,下面简单介绍网站目录文件权限的基本设定. 我们假设http服务器运行的用户和用户组是www,网站用户为cen ...

  6. IBM Intel 微软

    IBM是全球IT第一巨头,也是一个很奇特也很强大强大的公司,从螺丝钉键盘鼠标到CPU硬盘内存到大型机巨型机,它都可以制造,从软件到硬件到服务,它都可以提供,这在IT历史上,是否绝后我不敢说,空前应该是 ...

  7. 转载:如何优雅的实现INotifyPropertyChanged接口

    转载来源:http://www.cnblogs.com/TianFang/p/6240933.html 如何优雅的实现INotifyPropertyChanged接口 INotifyPropertyC ...

  8. Pyinstaller如何将资源文件一起打包至exe中

    基本原理:Pyinstaller 可以将资源文件一起bundle到exe中,当exe在运行时,会生成一个临时文件夹,程序可通过sys._MEIPASS访问临时文件夹中的资源 官方说明:https:// ...

  9. 通过锁字符串达到控制并发的效果C&num;

    lock锁的是地址 而.net有内部机制使得相同的字符串内存地址是相同的(new string)除外 下面上实验代码 using System; using System.Collections.Ge ...

  10. iOS登录单例

    iOS登录单例 一,工程图. 二,代码. UserInfo.h #import <Foundation/Foundation.h> @interface UserInfo : NSObje ...