最优合并问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定k 个排好序的序列s1 , s2,……, sk , 用2 路合并算法将这k 个序列合并成一个序列。假设所采用的2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。
为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。
对于给定的k个待合并序列，计算最多比较次数和最少比较次数合并方案。

Input

输入数据的第一行有1 个正整数k（k≤1000），表示有k个待合并序列。接下来的1 行中，有k个正整数，表示k个待合并序列的长度。

Output

输出两个整数，中间用空格隔开，表示计算出的最多比较次数和最少比较次数。

Sample Input

4
5 12 11 2

Sample Output

78 52

Hint

Source

使用优先队列优化，使用模板

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 template<typename T>
 5 int result(T q){//使用模板  因为求最大 最小值 ，这两个 代码几乎一样
 6     int rst=0;
 7     while((int)q.size()>2){//两个求和
 8         int sum=0;
 9         for(int i=0;i<2;i++){
10             sum+=q.top();
11             q.pop();
12         }
13         rst+=sum;
14         q.push(sum);
15     }
16     while(!q.empty()){
17         rst+=q.top();
18         q.pop();
19     }
20     return rst;
21 }
22 int main()
23 {
24     priority_queue<int,vector<int>,less<int> > q;//从大到小  Max
25     priority_queue<int,vector<int>,greater<int> > p;// 从小 到大 Min
26     int n,data;
27     cin>>n;
28     for(int i=0;i<n;i++){
29         cin>>data;
30         q.push(data);
31         p.push(data);
32     }
33     int  maxNum=result(q);//2 路合并算法合并2 个长度分别为m和n的序列需要m + n -1次比较 
34     int  minNum=result(p);
35     cout<<maxNum-(n-1)<<" "<<minNum-(n-1)<<endl;// 所以总共 比较n-1次  最后减去 n-1即可
36     return 0;
37 }

初始：未优化

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5     priority_queue<int,vector<int>,less<int> > q;//从大到小  Max
 6     priority_queue<int,vector<int>,greater<int> > p;// 从小 到大 Min
 7     int n,data;
 8     cin>>n;
 9     for(int i=0;i<n;i++){
10         cin>>data;
11         q.push(data);
12         p.push(data);
13     }
14     int  maxNum=0;//初始化 最大 费用 0
15     int  minNum=0;//初始化 最小 费用 0
16     while((int)q.size()>2){
17         int sumMax=0,sumMin=0;
18         for(int i=0;i<2;i++){
19             sumMax+=q.top();
20             q.pop();
21             sumMin+=p.top();
22             p.pop();
23         }
24         maxNum+=sumMax;
25         minNum+=sumMin;
26         q.push(sumMax);
27         p.push(sumMin);
28     }
29     while(!q.empty()){
30         maxNum+=q.top();
31         minNum+=p.top();
32         q.pop();
33         p.pop();
34     }
35     cout<<maxNum-(n-1)<<" "<<minNum-(n-1)<<endl;
36     return 0;
37 }

使用数组

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 
 6 bool cmp(int a, int b){
 7     return a>b;
 8 }
 9 
10 int main(){
11     int k;
12     int a[1010], b[1010];
13     int Min = 0, Max = 0;//此算法 ，和优先队列 差不多，每次将 算出的 最小值，最大值，在放进队列中 ，进行比较
14     cin>>k;
15     for(int i=0; i<k; i++){
16         cin>>a[i];
17         b[i]= a[i];
18     }//当取最小值保证每次的2个加数为最小便可，最大值同理取当前最大的两个值便可
19     sort(a, a+k);//最小值 排序 从小到大
20     sort(b, b+k, cmp);// 将 数据 从大到小 排序
21     for(int i=0; i<k-1; i++){
22         a[i+1] = a[i]+a[i+1];//当前 开始的 下一个 值  替换为   前两个 数之和，
23         Min += a[i+1];//最小值 更新 为 两个 最小值   最后 才算了 -(k-1)  因为 k 个数 ，要进行 k-1次比较 ，得减去 k-1 个 1  ； k-1次 （m+n-1）
24         sort(a+i+1, a+k);
25 
26         b[i+1] = b[i]+b[i+1];//此处为 最大值 ，每次加过 之和，在放进 要进行合并的序列中  在进行参与比较
27         Max += b[i+1];
28         sort(b+i+1, b+k ,cmp);
29     }
30     cout<<Max-k+1<<' '<<Min-k+1<<endl;
31     return 0;
32 }

 1 函数模板的声明形式为：
 2 template<typename（或class) T>
 3 <返回类型><函数名>(参数表)
 4 {
 5 函数体
 6 }
 7 其中，template是定义模板函数的关键字；template后面的尖括号不能省略；typename（或class)是声明数据类型参数标识符的关键字，用以说明它后面的标识符是数据类型标识符。这样，在以后定义的这个函数中，凡希望根据实参数据类型来确定数据类型的变量，都可以用数据类型参数标识符来说明，从而使这个变量可以适应不同的数据类型。例如：
 8 template<typename（或class) T>
 9 T fuc(T x, T y)
10 {
11 T x;
12 //……
13 }