p-7-13最优合并问题
程序员文章站
2024-03-16 09:27:40
...
1. 题目描述
给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序,使所需的总比较次数最少。
为了进行比较,还需要确定合并这个序列的最差合并顺序,使所需的总比较次数最多。
对于给定的k个待合并序列,计算最多比较次数和最少比较次数合并方案
2. 输入描述
输入数据的第一行有1 个正整数k(k≤1000),表示有k个待合并序列。接下来的1 行中,有k个正整数,表示k个待合并序列的长度
3.输出描述
输出两个整数,中间用空格隔开,表示计算出的最多比较次数和最少比较次数
4.输入样例
4
5 12 11 2
5.输出样例
78 52
6.解法一(解题思路)
例:4 5 12 11 2(这些是序列的长度)
排序2,4,5,11,12
贪心策略:每次选最小的序列合并得到最少比较次数;每次选最大的序列合并得到最多比较次数
2 个长度分别为m和n的序列需要m + n -1次比较
最多比较次数=(12+11-1)+ (12+11+5-1 )+ (12+11+5 +4 -1)+ (12+11+5+4+2-1 )
最少比较次数=(2+4-1)+(5+2+4-1)+(11+2+4+5-1)+(12+2+4+5+11-1)
#include <bits/stdc++.h>
using namespace std;
int getMin(int a[], int k){
int min_sum = 0, min_mark = 0;
for(int i = 1; i < k; i++){
min_sum += a[min_mark] + a[min_mark + 1] - 1;
a[min_mark] = a[min_mark] + a[min_mark + 1];
a[min_mark + 1] = 0;
min_mark++;
sort(a, a + k); //系统默认升序排序
}
return min_sum;
}
int getMax(int b[], int k){
int max_sum = 0, max_mark =0;
for(int i = 1; i < k; i++){
max_sum += b[k -1] + b[k - 2] - 1;
b[k - 1] = b[k - 1] + b[k -2];
b[k - 2] = 0;
sort(b, b + k);//系统默认升序排序
}
return max_sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0); // 优化编译速度
int k;
cin >> k;
int a[k], b[k];
for(int i = 0; i < k; i++)
cin >> a[i];
sort(a, a + k); //系统默认升序排序
for(int j = 0; j < k; j++)
b[j] = a[j];
cout << getMax(b, k) << " " << getMin(a, k);
return 0;
}
6. 解法二
#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q1; // 大根堆
priority_queue<int, vector<int>, greater<int> >q2; // 小根堆
int f(){
int max_sum = 0, min_sum = 0, a, b;
while(q1.size() > 1){
a = q1.top();
q1.pop();
b = q1.top();
q1.pop();
int sum = a + b;
max_sum += (sum -1);
q1.push(sum);
a = q2.top();
q2.pop();
b = q2.top();
q2.pop();
sum = a + b;
min_sum += (sum -1);
q2.push(sum);
}
cout << max_sum << " " << min_sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0); // 优化编译速度
int k;
cin >> k;
int x;
for(int i = 0; i < k; i++){
cin >> x;
q1.push(x);
q2.push(x);
}
f();
return 0;
}
上一篇: 二分搜索技术
下一篇: 算法笔记---简单折半查找