P1334 瑞瑞的木板
2018-06-17 22:25:31来源:未知 阅读 ()
题目描述
瑞瑞想要亲自修复在他的一个小牧场周围的围栏。他测量栅栏并发现他需要N(1≤N≤20,000)根木板,每根的长度为整数Li(1≤Li≤50,000)。于是,他神奇地买了一根足够长的木板,长度为所需的N根木板的长度的总和,他决定将这根木板切成所需的N根木板。(瑞瑞在切割木板时不会产生木屑,不需考虑切割时损耗的长度)瑞瑞切割木板时使用的是一种特殊的方式,这种方式在将一根长度为x的模板切为两根时,需要消耗x个单位的能量。瑞瑞拥有无尽的能量,但现在提倡节约能量,所以作为榜样,他决定尽可能节约能量。显然,总共需要切割N-1次,问题是,每次应该怎么切呢?请编程计算最少需要消耗的能量总和。
输入输出格式
输入格式:第一行: 整数N,表示所需木板的数量
第2到N+1行: 每行为一个整数,表示一块木板的长度
输出格式:一个整数,表示最少需要消耗的能量总和
输入输出样例
3 8 5 8
34
说明
将长度为21的木板,第一次切割为长度为8和长度为13的,消耗21个单位的能量,第二次将长度为13的木板切割为长度为5和8的,消耗13个单位的能量,共消耗34个单位的能量,是消耗能量最小的方案。
小根堆
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #define lli long long int 7 using namespace std; 8 void read(lli & n) 9 { 10 char c='+';lli x=0;lli flag=0; 11 while(c<'0'||c>'9') 12 { 13 c=getchar(); 14 if(c=='-')flag=1; 15 } 16 17 while(c>='0'&&c<='9') 18 x=x*10+c-48,c=getchar(); 19 if(flag==1)n=-x; 20 else n=x; 21 } 22 priority_queue<lli,vector<lli>,greater<lli> >q; 23 lli n,p; 24 lli ans; 25 int main() 26 { 27 read(n); 28 for(int i=1;i<=n;i++) 29 { 30 read(p); 31 q.push(p); 32 } 33 for(int i=1;i<=n-1;i++) 34 { 35 lli x=q.top(); 36 q.pop(); 37 lli y=q.top(); 38 q.pop(); 39 x=x+y; 40 ans+=x; 41 q.push(x); 42 } 43 cout<<ans; 44 return 0; 45 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:P1909 买铅笔
- 洛谷P1333 瑞瑞的木棍(欧拉回路) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash