一、实践题目

7-1 最优合并问题

题目描述：存在k个排好的序列，要用二路合并算法将其合并成一个序列。将长度

为m和长度为n的序列合并需要比较m+n-1次，现在要求进行合并操作时，所需要的

总比较次数最多和最少的次数。输入k，接下来的k个数为k个序列的长度

样例1：

//输入45 12 11 2 //输出78 52

题目分析：

容易分析得出，如果每次都将长度最小的两个序列合并，则每次合并的比较次数都会是最小的，

不断合并至为一个序列时，所需要的比较总次数最小。相反如果每次都将长度最大的两个序列

合并，则每次合并的比较次数都是最大的，最后得到的比较次数最多。

实现：

由题目分析可知，需要不断的将序列进行排序，因为每次合并后就会出现一个新的序列，又要将

新序列放入旧序列中重新排序，然后取出最小两个值再次合并，直到序列中仅存在一个值，则表

示合并完成。由上述分析可知，可以将序列长度按升序排序和降序排序然后不断合并在更新，就

可以得出结果因为需要不断排序，显然这里可以利用大根堆和小根堆进行操作，即可以借用C++

STL中的优先队列实现，定义优先级之后，每次取出队列中前两个元素合并并且用一个变量累加记

录比较次数，然后在将合并后的序列入队，不断进行该操作，直到队列中的只存在一个元素为止。

代码：

#include
     
      #include
      
       using namespace std;priority_queue
       
        que;                //大根堆 priority_queue
        
         
          ,greater
          
            >que1; //小根堆 int a;int main(){ int n; cin>>n; for(int i=0;i
           
            >a; que.push(a); que1.push(a); } int ans1=0; while(que.size()>1) { int a=que.top();que.pop(); //取出队首两个元素 int b=que.top();que.pop(); ans1+=(a+b-1); //记录比较次数 que.push(a+b); //合并后的新序列入队 } int ans2=0; while(que1.size()>1) { int a=que1.top();que1.pop(); int b=que1.top();que1.pop(); ans2+=(a+b-1); que1.push(a+b); } cout<
            
             <<' '<
             
              <
             
            
           
          
         
        
       
      
     

算法复杂度分析：

空间复杂度：改程序通过两个队列来实现，因此空间复杂度为O(n)。

时间复杂度：优先队列入队的时间复杂度为O(logN)，共有k个序列需要进行(k-1)次入队，因此时间复杂度为O(nlogn).

心得体会：

通过本次实践操作，对贪心算法的理解更加深刻，知道该如何分析贪心策略来求得所需要的答案，希望能通过不断练习更进一步。