题目:点击打开链接
题意:每次多多可以把最小的两堆放在一起,一直到只剩下一对为止。
思路:给所有的堆大小排序,每次从队列里取出最小的两个值,
这两个数的和再次加到队列中,知道队列里只剩下一个数。
关键是,每次从队列里拿出一个数时,要记得把这个字符删除,
这样就可以不断减少优先队列的长度了。
用数组做了一下,TLE了,果断换优先队列。
Description
在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有
的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,
所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合
并所消耗体力之和。
Input
第一行是一个整数n(1<=n<=10000),表示果子的种类数。第二行包含n个整数,用空格分隔,
第i个ai(1<=ai<=20000)是第i个果子的数目。
Output
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于2^31。
Sample Input
3
1 2 9
Sample Output
15
先把数组写的拿出来。
<span style="font-size:14px;">#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <map> using namespace std; int st[10005]; int main() { int n; int i; while(scanf("%d",&n)!=EOF) { int num = 0; int ans = 0; for(i=0;i<n;i++) { scanf("%d",&st[i]); } for(i=0;i<n-1;i++) { sort(st,st+n); ans = st[0]+st[1]; if(st[i]==1e9) break; num = num + ans; st[i] = 1e9; st[i+1] = ans; } printf("%d\n",num); } return 0; }</span>
接下来是正确的优先队列写法。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue>//头文件 #include <map> using namespace std; struct cmp//函数从小到大排序,因为默认的优先队列是从大到小排序 { bool operator ()(int &a,int &b) { return a>b; } }; int main() { priority_queue<int,vector<int>,cmp>q;//优先队列定义方式 int n; int i; int a; while(scanf("%d",&n)!=EOF) { int x=0,y=0; int ans = 0,sum = 0; for(i=0;i<n;i++) { scanf("%d",&a); q.push(a);//把a加入到优先队列q中 } while(!q.empty())//当队列里还有数存在时 { x = q.top();//从队列中取出 q.pop();//把队列中的第一个字符删除 if(q.empty())//这个是必须有的 break; y = q.top(); q.pop(); ans = x+y; sum = sum + ans; q.push(ans);//把ans加入到新队列里 } printf("%d\n",sum); } return 0; }