实践题目
7-1 最优合并问题
问题描述
题目来源：王晓东《算法设计与分析》
给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。 假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设 计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。 为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。
算法描述
最小次数：每次找最小的两个数字合并得到当前操作数，将两个最小的数字去掉，将合并得到的数字加入数组，往复操作即可得到最小操作数
（这题可以用一个哈夫曼树的思想维护，或者用multiset来维护，就可以在log的时间完成操作，时间复杂度度应该是O(NlogN)级别的）
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int b[1000005];
bool cmp(int aa,int bb)
{
return aa>bb;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
b[i]=a[i];
}
sort(a,a+n);
sort(b,b+n,cmp);
int cnt1=0,cnt2=0;
long long int s1=0,s2=0;
int kkk=0;
while(cnt1!=n-1)
{
sort(a,a+n+cnt1);
kkk=a[0]+a[1];
s1+=kkk-1;
a[n+cnt1]=kkk;
a[0]=100000000;
a[1]=100000000;
cnt1++;
}
while(cnt2!=n-1)
{
sort(b,b+n+cnt2,cmp);
kkk=b[0]+b[1];
s2+=kkk-1;
b[n+cnt2]=kkk;
b[0]=-1;
b[1]=-1;
cnt2++;
}
cout<<s2<<" "<<s1<<endl;
}
//4
//5 12 11 2
算法时间及空间复杂度分析（要有分析过程）
空间复杂度明显是O(N)的；
时间复杂度，每次操作都是O（NlogN）所以总的复杂度是O(N^2logN)的
心得体会（对本次实践收获及疑惑进行总结）
感觉队友的编程能力提高了