7-116 修理牧场(25 分)

2023-10-23 10:58
文章标签 25 修理 牧场 116

本文主要是介绍7-116 修理牧场(25 分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

7-29 修理牧场(25 分)

农夫要修理牧场的一段栅栏,他测量了栅栏,发现需要N块木头,每块木头长度为整数Li个长度单位,于是他购买了一条很长的、能锯成N块的木头,即该木头的长度是Li的总和。

但是农夫自己没有锯子,请人锯木的酬金跟这段木头的长度成正比。为简单起见,不妨就设酬金等于所锯木头的长度。例如,要将长度为20的木头锯成长度为8、7和5的三段,第一次锯木头花费20,将木头锯成12和8;第二次锯木头花费12,将长度为12的木头锯成7和5,总花费为32。如果第一次将木头锯成15和5,则第二次锯木头花费15,总花费为35(大于32)。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:

输入首先给出正整数N104),表示要将木头锯成N块。第二行给出N个正整数(50),表示每段木块的长度。

输出格式:

输出一个整数,即将木头锯成N块的最少花费。

输入样例:

8
4 5 1 2 1 3 1 1

输出样例:

49

我的代码:

#include<iostream>
#include<queue>
using namespace std;
int n,i,a[100001],sum=0;
int main()
{priority_queue<int,vector<int>,greater<int> > q;cin>>n;for(i=0;i<n;i++) cin>>a[i];for(i=0;i<n;i++) q.push(a[i]);while(q.size()>1){int x,y;x=q.top();q.pop();y=q.top();q.pop();q.push(x+y);sum=sum+x+y;}printf("%d\n",sum);return 0;
}

这篇关于7-116 修理牧场(25 分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/267385

相关文章

【JavaScript】LeetCode:21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心:连续和(count)< 0时,放弃当前起点的连续和,将下一个数作为新起点,这里提供使用贪心算法解决本题的代码。动态规划:dp[i]:以nums[i]为结尾的最长连续子序列(子数组)和。 dp[i] = max(dp[i - 1]

【uva】116-Unidirectional TSP(动态规划,路径问题)

一道很基础的动态规划,不过需要考虑路径(而且是最小字典序)。 转移方程很好写: d[i][j] = min(dp[i + 1][ j] ,dp[i + 1][j - 1] ,dp[i + 1][ j - 1]) + mat[j[i]; dp[i][j]代表走到第i列第行的时候距离最后一行的最短距离; 13991881 116 Unidirectional TSP Accepted C

2025年25届计算机毕业设计:如何实现高校实验室Java SpringBoot教学管理系统

✍✍计算机毕业编程指导师** ⭐⭐个人介绍:自己非常喜欢研究技术问题!专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目:有源码或者技术上的问题欢迎在评论区一起讨论交流! ⚡⚡ Java、Python、微信小程序、大数据实战项目集 ⚡⚡文末获取源码 文章目录 ⚡⚡文末获取源码高校实验室教学管理系统-研究背景高校实验室教学管理系

智力题:25匹马5条跑道找最快的3匹马,最少需要跑几次?

要找出25匹马中最快的3匹马,使用5条跑道,最少需要跑几次?我们可以通过逐步推理来解决这个问题。 第一步:分组比赛 首先,我们将25匹马分成5组,每组5匹马。每组进行一次比赛,这样我们就有5次比赛的结果。 组1:A1, A2, A3, A4, A5 组2:B1, B2, B3, B4, B5 组3:C1, C2, C3, C4, C5 组4:D1, D2, D3, D4, D5 组

芬兰手游业25年发展史

自2010年Rovio凭借《愤怒的小鸟》成功以来,芬兰的优秀开发者可以说是不断的引领手游潮流,有Frogmid、Seriously这样的小型团队,也有Supercell这样的世界收入冠军。除却收入之外,我们可以发现芬兰开发商的手游绝大多数都是具有独特创意的。 为什么芬兰手游业可以具有如此之大的竞争优势?其他人想要赶上应该怎么做?这个答案从来都不是能够简单作答的,因为它根植于芬兰的行业发展史,所以

图形API学习工程(25):实现法线贴图

工程GIT地址:https://gitee.com/yaksue/yaksue-graphics 目标 在《图形API学习工程(10):基础光照》中,我实现了最基础的光照,同时也表现了法线的作用。 在《图形API学习工程(11):使用纹理》中,工程已经能够加载纹理贴图。 这样,法线贴图 所需的准备已经完成,可以在工程里实现这个技术了。 (关于法线贴图的意义,可见上一篇博客《从“法线贴图的意义

【简历】25届南京某一本JAVA简历:简历通过率还好,但是拿不到OFFER

注:为保证用户信息安全,姓名和学校等信息已经进行同层次变更,内容部分细节也进行了部分隐藏 简历说明 今天看一份25届南京某一本大学的Java简历。 这个简历呢,学校是一本。我们说上来先要定校招层次,这个层次就按照中厂来讲。因为现在很多的双非一本目标都是在中厂。 这个同学有个实习经历,一本有八成的同学主项目都是重复的。HR他只能看到项目重不重复,要点对不对他不知道,就从这个角度来看,这位同学

GNU的伪操作 (25)

这里主要是 对 GNU的 各个伪操作进行 详细的解释。 先来看着几个 伪操作。 .byte,  .short,  .long,  .quad , .float ,  这个是关于 字节的。 .string   .ascii 是关于字符串的。 这个字符串编译器是可以自动在末尾补0 的。 举例: val:         .word 0x11223344         m

25版王道数据结构课后习题详细分析 第八章 8.2 插入排序

一、单项选择题 ———————————————————— ———————————————————— 解析:直接插入排序在最坏的情况下要做n(n-1)/2次关键字的比较,当n=5时, 关键字的比较次数为10。注意不考虑与哨兵的比较。 正确答案: ———————————————————— ———————————————————— 解析:由于序列初始基本有序,因此使用直接插入排序

游卡,三七互娱,得物,顺丰,快手,oppo,康冠科技,途游游戏,埃科光电25秋招内推

游卡,三七互娱,得物,顺丰,快手,oppo,康冠科技,途游游戏,埃科光电25秋招内推 ①顺丰 【招聘岗位】研发、算法、大数据、产品、项管、设计、人资等 【官方内推码】4FOLXH 【一键内推】https://sourl.cn/UzbDat ②游卡 【岗位】程序技术、产品策划、美术、发型运营、职能综合、桌游业务等大类 【一键内推】https://sourl.cn/PHiZZE 【内推码】DSymt