NYOJ-055初识C++STL之priority_queue

碎语

其实这道题是典型的Huffman Tree,最开始做的时候是用数组来实现队列的FIFO特性,但是提交后发现O(N)太高了,OJ总是报TLE,尝试优化未果之后,骆老师说堆排序试试,用priority_queue优先队列完美AC,堆排序的时间复杂度我们一般认为可以近似到O(nlogn)。emmm,不说废话了,开始讲正题。

关于priority_queue

priority_queue#include <queue>中,我们用之前先声明一下,值得提的是优先队列在使用的过程中是会自动排序的,这一点尤为重要。

1
2
3
4
5
6
priority_queue <int> i;
priority_queue <double> d;
priority_queue <node> q;//结构体
priority_queue <int,vector<int>,greater<int> > q;//greater升序
//#include<vector>可以省略
priority_queue <int,vector<int>,less<int> >q;//less降序

我们先声明一个名为qpriority_queue

1
priority_queue<int,vector<int>,greater<int> >q;//缺省升序

则可以对其进行以下操作

1
2
3
4
5
6
q.size();//返回队列q元素个数
q.empty();//确定队列q是否为空,空则return 1,反之 return 0
q.push(k);//在队列q的末尾插入(压入)元素k
q.pop();//弹掉队列q的第一个元素
q.top();//取出队列q的第一个元素
q.back();//取出队列q的末尾元素

题目描述:

  小明很想吃果子,正好果园果子熟了。在果园里,小明已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。小明决定把所有的果子合成一堆。 因为小明比较懒,为了省力气,小明开始想点子了:
  每一次合并,小明可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。小明在合并果子时总共消耗的体力等于每次合并所耗体力之和。
  因为还要花大力气把这些果子搬回家,所以小明在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值。
  例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以小明总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入描述:
第一行输入整数N(0< N< =10)表示测试数据组数。接下来每组测试数据输入包括两行,第一行是一个整数n(1<=n<=12000),表示果子的种类数。第二行包含n个整数,用空格分隔,第i个整数ai(1<=ai<=20000)是第i种果子的数目。
输出描述:
每组测试数据输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。
样例输入:

1
3
1 2 9

样例输出:

15

使用数组模拟实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*time:3828ms memory:2024k*/
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

long long test(int queue[],int x) {
long long power=0;
int beg=1;
for(int i=1; i<x; i++) {
power+=queue[i]+queue[i-1];//最小的两个值相加
queue[i]+=queue[i-1];//更新[i]值,
queue[i-1]=0;//[i-1]置0;
sort(queue+beg,queue+x);//重新排序
beg++;
}
return power;
}

int main() {
int n;
int queue[12010];
cin>>n;
while(n--) {
int _num;
cin>>_num;
for(int i=0; i<_num; i++) {
cin>>queue[i];
}
sort(queue,queue+_num);//排序
cout<<test(queue,_num)<<endl;
}
return 0;
}

使用priority_queue实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*time:122ms memory:2168k*/
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>

using namespace std;

int main() {
int n;
cin>>n;
while(n--) {
int _num,a,b;
long long power=0;
priority_queue<int,vector<int>,greater<int> >q;//定义priority_queue
cin>>_num;
for(int i=0; i<_num; i++) {
int temp;
cin>>temp;
q.push(temp);//数据插入queue
}
if(q.size()==1) {
cout<<power<<endl;
break;//特殊值处理,为1时无需搬运
}
while(!q.empty()) {
a=q.top();//取出最小值
q.pop();//弹出该值
b=q.top();//取出队列最小值
q.pop();//弹出该值
power+=(a+b);//计入体力
if(!q.empty()) {
q.push(a+b);
//队列非空时压入队列 ,重新排序
}
}
cout<<power<<endl;
}
return 0;
}
Author: Junzhou Liu
Link: https://liujunzhou.top/2018/5/29/nyoj055/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
AliPay
WechatPay