1369:合并果子(fruit)

简介: 1369:合并果子(fruit)

1369:合并果子(fruit)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n−1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。

例如有3种果子,数目依次为1,2,9。可以先将 1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

【输入】

两行,第一行是一个整数n(1≤n≤30000),表示果子的种类数。第二行包含n个整数,用空格分隔,第i个整数ai(1≤ai≤20000)是第i种果子的数目。

【输出】

一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于231。

【输入样例】

3

1 2 9

【输出样例】

15

【提示】

【样例2输入】

10

3 5 1 7 6 4 2 5 4 1

【样例2输出】

120

1. #include <iostream>
2. #include <cstdio>
3. #include <algorithm>
4. #include <queue>
5. #include <cmath>
6. using namespace std;
7. int heap[100001],heap_len;//堆数组
8. int n,x,y,i,sum=0;
9. void put(int t){//将t加入小堆
10.   int now,next;
11.   heap[++heap_len]=t;
12.   now=heap_len;
13.   while(now>1){
14.     next=now/2;
15.     if(heap[now]>=heap[next]) return;
16.     swap(heap[now],heap[next]);
17.     now=next; 
18.   }
19. }
20. int get(){//弹出小堆堆顶元素
21.   int next,tot,now;
22.   tot=heap[1];
23.   heap[1]=heap[heap_len--];
24.   now=1;
25.   while(2*now<=heap_len){
26.     next=2*now;
27.     if(next<heap_len&&heap[next+1]<heap[next])
28.       next++;
29.     if(heap[next]>=heap[now]) return tot;
30.     swap(heap[now],heap[next]);
31.     now=next;
32.   }
33.   return tot;
34. }
35. int main()
36. {
37.   scanf("%d",&n);
38.   for(i=1;i<=n;i++){
39.     scanf("%d",&x);
40.     put(x);
41.   }
42.   for(i=1;i<n;i++){
43.     x=get();
44.     y=get();
45.     sum+=x+y;
46.     put(x+y);
47.   }
48.   printf("%d\n",sum);
49.   return 0;
50. }


相关文章
|
前端开发 开发者 容器
|
关系型数据库 MySQL Linux
【Linux】jdk & Tomcat & MySql的安装及Linux后端接口部署
【Linux】jdk & Tomcat & MySql的安装及Linux后端接口部署
249 0
|
存储 关系型数据库 MySQL
云计算|OpenStack|社区版OpenStack安装部署文档(四 --- 镜像服务glance安装部署---Rocky版)
云计算|OpenStack|社区版OpenStack安装部署文档(四 --- 镜像服务glance安装部署---Rocky版)
387 0
|
10月前
|
前端开发 JavaScript 开发者
React与Vue:前端框架的巅峰对决与选择策略
【10月更文挑战第23天】 React与Vue:前端框架的巅峰对决与选择策略
|
10月前
|
人工智能 弹性计算 数据可视化
解决方案|触手可及,函数计算玩转 AI 大模型 评测
解决方案|触手可及,函数计算玩转 AI 大模型 评测
159 1
|
11月前
|
Dubbo Java 应用服务中间件
剖析Tomcat线程池与JDK线程池的区别和联系!
剖析Tomcat线程池与JDK线程池的区别和联系!
415 0
剖析Tomcat线程池与JDK线程池的区别和联系!
|
11月前
|
前端开发 UED 开发者
uni-app:去除导航栏&跨域的问题&blobe查看图片&v-deep&页面操作 (五)
本文介绍了几个前端开发技巧:1) 如何通过设置 `navigationStyle` 为 `custom` 去除顶部导航;2) 解决跨域问题的方法,包括使用 `dotenv` 加载全局变量和配置 `devServer` 的代理;3) 使用 Blob 和 FileReader 查看图片;4) 利用 `v-deep` 深度作用选择器修改样式;5) 修改页面左上角返回按钮的行为。
448 0
|
机器学习/深度学习 自然语言处理 监控
NLP技术有哪些主要任务?
【7月更文挑战第8天】NLP技术有哪些主要任务?
838 4
|
安全 Java 大数据
一文搞懂什么是“注解”
一文搞懂什么是“注解”
565 0
一文搞懂什么是“注解”
|
算法 Java C++
非启发式算法——二分、三分搜索算法
非启发式算法——二分、三分搜索算法
397 0