（贪心算法）PTA--最优合并问题

小鱼儿 2022-12-27 12:35 141阅读 0赞

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

输入格式:  
第一行有 1 个正整数k，表示有 k个待合并序列。 第二行有 k个正整数，表示 k个待合并序列的长度。

输出格式:  
输出最多比较次数和最少比较次数。

输入样例:  
在这里给出一组输入。例如：  
4  
5 12 11 2

输出样例:  
在这里给出相应的输出。例如：  
78 52

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    #define N 10000
    bool cmp(int a,int b){
        
        return a>b;
    }
    int max(int a[],int k){
        
    	sort(a,a+k,cmp);
    	int maxs=a[0]+a[1]-1;
    	int t=a[0]+a[1]-1;
    	for(int i=2;i<k;i++){
        
    	    t+=a[i];
    		maxs+=t;
    	}
    	return maxs;
    }
    int min(int a[],int k){
        
         sort(a,a+k);
    	 int mins=0;
    	 for(int i=0;i<k-1;i++){
        
    	     mins+=a[i]+a[i+1]-1;
    		 a[i]=a[i]+a[i+1];
    		 a[i+1]=0;
    		 sort(a,a+k);
    	 }
    	 return mins;
    }
    int main(){
        
         int k,m,n;
    	 int a[N];
    	 scanf("%d",&k);
    	 for(int i=0;i<k;i++){
        
    	     scanf("%d",&a[i]);
    	 }
    	 m=max(a,k);
    	 n=min(a,k);
    	 printf("%d %d\n",m,n);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关【贪心算法】最优装载问题C++语言

文章目录问题描述问题分析算法步骤举例代码问题描述

àì夳堔傛蜴生んèń/ 2023年03月12日 12:13/ 0 赞/ 190 阅读

相关算法设计与分析——贪心算法——最优装载问题

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 include<ios

电玩女神/ 2023年01月16日 11:28/ 0 赞/ 202 阅读

相关（贪心算法）PTA--最优合并问题

给定k 个排好序的序列, 用 2 路合并算法将这k 个序列合并成一个序列。假设所采用的 2 路合并算法合并 2 个长度分别为m和n的序列需要m+n-1 次比较。试设计一个算

小鱼儿/ 2022年12月27日 12:35/ 0 赞/ 142 阅读

相关（贪心算法）PTA--装箱问题、月饼问题

1.装箱问题 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

r囧r小猫/ 2022年12月27日 12:35/ 0 赞/ 192 阅读

相关贪心算法（最优装载问题）

加勒比海盗船海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值。虽然海盗船足够大，但载重量为 C ，每件古董的重量为 W

古城微笑少年丶/ 2022年09月10日 03:30/ 0 赞/ 309 阅读

相关贪心算法1：贪心的概念最优装载问题

> 贪心算法的原理：贪心算法总是做出当前最好的选择，也就是说，它期望通过局部最优选择从而得到全局最优的解决方案。 1. 没有后悔药，一旦做出选择，不可以后悔； 2. 有

谁借莪１个温暖的怀抱￠/ 2022年05月08日 10:08/ 0 赞/ 307 阅读

相关 1743 最优合并问题

最优合并问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定k 个排好序的序列s

雨点打透心脏的1/2处/ 2022年04月24日 09:52/ 0 赞/ 174 阅读

相关最优合并问题

最优合并问题 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给定k 个排好序的序列s

深碍√TFBOYSˉ_/ 2022年02月16日 15:06/ 0 赞/ 184 阅读

相关最优合并问题

最优合并问题 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem

た入场券/ 2022年02月15日 04:25/ 0 赞/ 174 阅读

相关贪心算法（3）：最优服务次序问题

题目设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1≦i ≦n 。有1处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时

拼搏现实的明天。/ 2022年02月04日 04:09/ 0 赞/ 378 阅读