codevs 1063 合并果子 优先队列相关

2023-11-11 10:10

本文主要是介绍codevs 1063 合并果子 优先队列相关,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1063 合并果子

 2004年NOIP全国联赛普及组
 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
题目描述 Description

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


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


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


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

输入描述 Input Description

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

输出描述  Output Description

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

样例输入 Sample Input


1 2 9

样例输出 Sample Output

15

数据范围及提示 Data Size & Hint

对于30%的数据,保证有n<=1000: 
对于50%的数据,保证有n<=5000; 
对于全部的数据,保证有n<=10000。

------------------------------------------------------------------------------------------------------------------------

刚开始没看清题意,以为要按照顺序合并,结果码了DP;后来明白题意后,才知道这道题并不难,运用优先队列水过。

讲一下优先队列:

普通的队列的元素遵循先进先出,后进后出的原则,但在优先队列里,每个元素被赋予优先级,优先级较高的最先出列。定义优先队列时默认为大根堆,即元素越大优先级越高,越先出列

看了别人的博客才知道:优先队列的时间复杂度为O(logn),n为队列中元素的个数,其存取都需要时间。

优先队列用之前需声明:

#include<queue>

using namespace std;

priority_queue <元素类型> 队列名;

五种操作(例如声明了一个这样的优先队列:priority_queue <int> que):

que.push(x) //往队列中添加一个元素x;

que.top() //取出队头元素,但不删除;

que.pop() //删除队头元素;

que.size() //返回队列中元素的个数;

que.empty() //判断队列是否为空,若为空,则为真,反之则反。

P.S. 若要把队列变成“小根堆”,可以push(-x),在元素前加个负号,取出时再把负号去掉。

AC代码:

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 #include<queue>
 5 using namespace std;
 6 priority_queue <int> que;
 7 int n;
 8 long long ans;
 9 int main()
10 {
11     scanf("%d",&n);
12     for(int i=1,x;i<=n;i++){
13         scanf("%d",&x);
14         que.push(-x);
15     }
16     ans=0;
17     for(int i=1;i<n;i++){
18         int tmp=que.top();
19         que.pop();
20         tmp+=que.top();
21         ans-=tmp;
22         que.pop();
23         que.push(tmp);
24     }
25     printf("%lld",ans);
26     return 0;
27 }
优先队列

 

-------------------------------------------------------------------------------------------------------------------

因为有需要用到元素为结构体类型的优先队列,故又回来学习了一波。

要想实现元素为结构体类型,需要定义重载运算符,以队列dd为例,可以分为两种。

第一种是在结构体定义外定义重载运算符:

1 struct node{
2     int a,b;
3 };
4 bool operator <(const node& x,const node& y){
5     return x.a < y.a; //大根堆 
6 } 
7 priority_queue<node> dd;
外定义

以上情况为大根堆,注意x,y位置不能颠倒,可以这样记忆:队列队头一般在最右边,大根堆的队头为最大,所以为小于号;如果为大于号,则为小根堆。

另一种当然为内定义:

1 struct node{
2     int a,b;
3     bool operator < (const node& t)const{
4         return a<t.a;//大根堆 
5     }
6 };
7 priority_queue<node> dd;
内定义

以上情况也为大根堆,同样a和t.a的位置不能颠倒;如果为大于号,则为小根堆。

这样定义之后,以上的优先队列操作正常使用,只是添加的元素,要为结构体类型,以上为例:node t;dd.push(t);

测试代码:

操作:给出n个元素,把队中元素按参数a从大到小输出,若a相等,则按参数b从小到大输出。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 using namespace std;
 5 struct node{
 6     int a,b;
 7     bool operator < (const node& t)const{  //内定义 
 8         if(a==t.a) return b>t.b;//小根堆 
 9         return a<t.a;//大根堆 
10     }
11 };
12 priority_queue<node> dd;
13 //bool operator <(const node& x,const node& y){  //外定义 
14 //    if(x.a==y.a) return x.b>y.b;//小根堆 
15 //    return x.a<y.a;//大根堆 
16 //}  
17 int n;
18 int main(){
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++){
21         node t;
22         scanf("%d %d",&t.a,&t.b);
23         dd.push(t);
24     }
25     for(int i=1;i<=n;i++) printf("%d %d\n",dd.top().a,dd.top().b),dd.pop();//把队中元素按参数a从大到小输出,若a相等,则按参数b从小到大输出 
26     return 0;
27 }
Test

 

转载于:https://www.cnblogs.com/lpl-bys/p/7397288.html

这篇关于codevs 1063 合并果子 优先队列相关的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/389306

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

sqlite3 相关知识

WAL 模式 VS 回滚模式 特性WAL 模式回滚模式(Rollback Journal)定义使用写前日志来记录变更。使用回滚日志来记录事务的所有修改。特点更高的并发性和性能;支持多读者和单写者。支持安全的事务回滚,但并发性较低。性能写入性能更好,尤其是读多写少的场景。写操作会造成较大的性能开销,尤其是在事务开始时。写入流程数据首先写入 WAL 文件,然后才从 WAL 刷新到主数据库。数据在开始

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页);内聚的类型;关于码制的知识点;地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位:为1时表示在内存期间被访问过,为0时表示未被访问;修改位:为1时表示该页面自从被装入内存后被修改过,为0时表示未修改过。 置换页面时,最先置换访问位和修改位为00的,其次是01(没被访问但被修改过)的,之后是10(被访问了但没被修改过),最后是11。 2.内聚的类型 功能内聚:完成一个单一功能,各个部分协同工作,缺一不可。 顺序内聚:

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点