目录
问题:果园里有N堆不同重量的果子,现在需要将它们合成一堆,每次只能合并两堆果子,并且消耗两堆果子重量和的能量,请问如何将所有果子合成一堆消耗最少的能量。
1 写出选择排序伪代码,分析算法复杂度
伪代码:
//算法:SelectSort(arr, n)
//输入:数组arr, 元素个数n
//输出:选择排序后的数组arr
for k<-1 to n do
j<-k
mini<-arr[j]
for j to n do
if mini > arr[j] then
mini<-arr[j]
index<-j
end if
end for
交换arr[index]和arr[k]的值
end for
return arr
复杂度分析:
选择排序的结构为双重循环且循环的次数与数组的大小n成正比关系,所以问题的规模为n。记每轮循环的操作次数为c,则算法的主要操作次数为C(n) = c,展开则为C(n) = c,求和则为C(n) = c(1 + 2 + …… + n) = n(n + 1)。所以复杂度为O()。
2 掌握STL中优先队列的使用方法
问题:果园里有N堆不同重量的果子,现在需要将它们合成一堆,每次只能合并两堆果子,并且消耗两堆果子重量和的能量,请问如何将所有果子合成一堆消耗最少的能量。
代码:
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int>myqueue;
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
int x;
cin >> x;
myqueue.push(-x);
}
int sum = 0;
while (!myqueue.empty()) {
int a = myqueue.top();
myqueue.pop();
if (myqueue.empty()) {
cout << abs(sum) << endl;
return 0;
}
else {
int b = myqueue.top();
myqueue.pop();
sum += a + b;
myqueue.push(a + b);
}
}
return 0;
}