P1334 瑞瑞的木板
2024-08-30 15:50:22
题目描述
瑞瑞想要亲自修复在他的一个小牧场周围的围栏。他测量栅栏并发现他需要N(1≤N≤20,000)根木板,每根的长度为整数Li(1≤Li≤50,000)。于是,他神奇地买了一根足够长的木板,长度为所需的N根木板的长度的总和,他决定将这根木板切成所需的N根木板。(瑞瑞在切割木板时不会产生木屑,不需考虑切割时损耗的长度)瑞瑞切割木板时使用的是一种特殊的方式,这种方式在将一根长度为x的模板切为两根时,需要消耗x个单位的能量。瑞瑞拥有无尽的能量,但现在提倡节约能量,所以作为榜样,他决定尽可能节约能量。显然,总共需要切割N-1次,问题是,每次应该怎么切呢?请编程计算最少需要消耗的能量总和。
输入输出格式
输入格式:
第一行: 整数N,表示所需木板的数量
第2到N+1行: 每行为一个整数,表示一块木板的长度
输出格式:
一个整数,表示最少需要消耗的能量总和
输入输出样例
输入样例#1:
3
8
5
8
输出样例#1:
34
说明
将长度为21的木板,第一次切割为长度为8和长度为13的,消耗21个单位的能量,第二次将长度为13的木板切割为长度为5和8的,消耗13个单位的能量,共消耗34个单位的能量,是消耗能量最小的方案。
小根堆
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define lli long long int
using namespace std;
void read(lli & n)
{
char c='+';lli x=;lli flag=;
while(c<''||c>'')
{
c=getchar();
if(c=='-')flag=;
} while(c>=''&&c<='')
x=x*+c-,c=getchar();
if(flag==)n=-x;
else n=x;
}
priority_queue<lli,vector<lli>,greater<lli> >q;
lli n,p;
lli ans;
int main()
{
read(n);
for(int i=;i<=n;i++)
{
read(p);
q.push(p);
}
for(int i=;i<=n-;i++)
{
lli x=q.top();
q.pop();
lli y=q.top();
q.pop();
x=x+y;
ans+=x;
q.push(x);
}
cout<<ans;
return ;
}
最新文章
- .NET牛人应该知道些什么
- elasticsearch-cn-out-of-box
- Poj(1511),SPFA
- Hibernate SQL方言 (hibernate.dialect)
- MySQL CURDATE() 函数
- Google Chrome中的高性能网络(二)
- Java学习之路(一)了解Java
- webstorm配置scss环境
- BZOJ_1208_[HNOI2004]宠物收养所_SPLAY
- MVC防止CSRF攻击
- Codeforces 1109E. Sasha and a Very Easy Test 线段树
- redis基本数据结构
- maven-resources-plugin插件关于占位符不生效问题
- Codeforces Round #548
- 研究傅里叶变换的一本好书<;<;快速傅里叶变换及其C程序>;>;
- Python 初识网络
- if语句引起的bug
- 【代码审计】iZhanCMS_v2.1 后台存在多个SQL注入漏洞分析
- 程序员 vs HR(皮这么一下很开心)
- RT-thread内核之IO设备管理系统
热门文章
- Ubuntu 16.04出现chmod: 无效模式:";a";的问题解决
- JDBC操作MySQL出现:This result set must come from a statement that was created with a result set type of ResultSet.CONCUR_UPDATABLE, ...的问题解决
- HDU 1030 数学题
- 【poj2774】Long Long Message
- 第一次PHP面试题
- Codeforces Round #363 (Div. 2)E. LRU
- 【HDU 2010】水仙花数
- MongoDB全文搜索——目前尚不支持针对特定field的搜索
- 【bug】Android版QQ浏览器广告过滤
- [NOI2018]冒泡排序