1743 最优合并问题

雨点打透心脏的1/2处 2022-04-24 09:52 156阅读 0赞

### 最优合并问题 ###

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

#include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
      int s[1010],a[1010];
      int n,sum1=0,sum2=0;
      std::cin >> n;
      for(int i = 0; i < n; i++){
        std::cin >> s[i];
        a[i] = s[i];
      }
      for(int i = 0; i < n-1; i++){
        sort(s+i,s+n);           //对i~n的数排序 每次取两个最小值
        sum1 = sum1 + s[i] + s[i+1];
        s[i+1] += s[i];
    
        sort(a,a+n-i);           //对0~n-i的数排序 每次取两个最大值
        sum2 = sum2 + a[n-1-i] + a[n-2-i];
        a[n-2-i] += a[n-1-i];
      }
      std::cout << sum2-n+1 << " " <<sum1-n+1 << '\n';
      return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

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

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

相关最优布线问题

最优布线问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述学校有n台计算机，为了

刺骨的言语ヽ痛彻心扉/ 2022年08月18日 02:30/ 0 赞/ 95 阅读

相关最优服务次序问题

最优服务次序问题 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述设有n 个顾客同时等待一项

不念不忘少年蓝@/ 2022年08月10日 05:57/ 0 赞/ 152 阅读

相关独立任务最优调度问题

> 独立任务最优调度问题 > 时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte > 总提交 : 212 测试通

你的名字/ 2022年06月14日 23:51/ 0 赞/ 157 阅读

相关最优装载问题（贪心基础）

最优装载问题。给出n个物体，第i个物体重量为w\[i\]。选择尽量多的物体，使得总重量不超过C。【分析】由于只关心物体的数量，所有装重的没有装轻的划算。只需把所有物

淩亂°似流年/ 2022年06月07日 08:42/ 0 赞/ 177 阅读

相关 1743 最优合并问题

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

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

相关动态规划——解决最优问题

说到动态规划，这里先简单看下另一个算法“贪心算法-greedy algorithm”，是一种在每一步选择中都采用在当前状态下最优或最好的选择，从而导致结果是最好或

骑猪看日落/ 2022年03月15日 10:14/ 0 赞/ 181 阅读

相关最优合并问题

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

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

相关最优合并问题

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

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