没有合适的资源?快使用搜索试试~ 我知道了~
算法设计与分析:多元Huffman编码
需积分: 40 3 下载量 168 浏览量
2020-12-06
15:48:27
上传
评论 1
收藏 37KB DOC 举报
温馨提示
试读
4页
问题描述:在一个操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆,合并的费用为新的一堆的石子数。
资源详情
资源评论
资源推荐
问题描述:在一个操场的四周摆放着 n 堆石子。现要将石子有次序
地合并成一堆。规定每次至少选 2 堆最多选 k 堆石子合并成新的一
堆,合并的费用为新的一堆的石子数。试设计一个算法,计算出将
n 堆石子合并成一堆的最大总费用和最小总费用。
算法设计:对于给定 n 堆石子,计算合并成一堆的最大总费用和最小
总费用。
数据输入:由文件 input.txt 给出输入数据。输入数据的第 1 行有 2
个正整数 n 和 k,表示有 n 堆石子,每次至少选 2 堆最多选 k 堆石
子合并。第 2 行有 n 个数,分别表示每堆石子的个数。
结 果 输 出 : 将计 算 出 的 最 大 总 费 用 和 最 小 总 费 用 输 出 到 文 件
output.txt,两个整数之间用空格分开。
算法分析:最大的花费,就要找最大的数重叠次数最多,所以与 k
无关,只需要从最大的开始,每次都选最大的两堆来相加就可以得
出最大的重叠次数。
最小的花费思路和最大的相同,要重迭次数最小,就要挑选 k 最大,
每次从最小的 k 堆开始合并。这里要做一步处理是如果最后不够 k
堆合并的时候要在整个队列的前面填 0(填零的意思就是一开始不
按照 k 堆合并,而是按照从 0-k 的一个数合并,这样后面的数重叠
次数才是最小的,如果不补零,后面大的数就会多重叠)。
#include<stdlib.h>
#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include<fstream>
m0_46694901
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0