贪心策略:请你最最小的金条分割代价

2023-11-11 06:10

本文主要是介绍贪心策略:请你最最小的金条分割代价,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

贪心策略:请你最最小的金条分割代价

提示:从本文开始,咱们来说贪心策略系列文章!!

贪心策略在互联网大厂的招聘笔试和面试中的地位!!!在笔试中考贪心,而面试不考贪心。

(1)贪心在笔试中:75%的考题都是贪心策略,为啥呢,一方面考你的聪明程度,另一方面,考你的代码编写能力;所以我参加过的笔试证明了这一点,往往大厂给你三个算法题,第1道题一定是贪心,排序结合的算法题,你需要懂点脑子,了解一下排序和堆啥的数据结构,还得会点贪心技巧,才能设计出来;
(2)面试不怎么考贪心策略,为什么?因为面试考你的是算法的优化能力,所以如果给你贪心的话,你一下子想到了解决方案,也不谈什么优化的事情,没意义,所以不考贪心。
(3)你必须要认识到:最简单的是国内的面试过程(嘴说的事情,都好办),难度中上等的是国外的笔试面试,最难的国内的算法笔试。 那么,你一定要明白,最难的还是国内的算法笔试题!!!因此要多练,多学,多见题,多思考,多总结,才能拿下。

以下是贪心策略基础题目系列文章:
(1)贪心策略:请你计算i×arr[i]的累加和最大值
(2)贪心策略:请你设计最优的安排会议日程表,以使得举行的会议数最多
(3)贪心策略:求一条街上最少应该放多少盏灯,才能照亮整条街的商户
(4)贪心策略:请你将字符串拼接,最终拼接好的字符串字典序最小


文章目录

  • 贪心策略:请你最最小的金条分割代价
    • @[TOC](文章目录)
  • 题目
  • 一、审题
  • 二、贪心策略:哈夫曼树
  • 总结

题目

给你一个数组arr,里面都是黄金的部分价值,整个arr是一条黄金
每次你切一刀,将金条一分为2,代价是两遍黄金总和
最后每一块都只能切到只剩一个部分
请你最最小的金条分割代价


一、审题

示例:arr= 10 20 30
有几种切法:
第一种:
第一刀切为10/ 20 30代价是10+20+30=60
第二刀切为10/20/30代价是20+30=50
总代价为110

第二种:
第一刀切为:10 20 / 30代价为30+30=60
第二刀切为:10/20 / 30代价为10+20=30
故总得代价为90

显然90更小


二、贪心策略:哈夫曼树

其实我们希望左右每次都是尽量相等而且尽量小
否则,你留一遍太大,切下去代价很费力

那就用哈夫曼树解决:
比如:
arr= 3,9,6,4,1
怎么切呢?要总代价最小,最后一刀尽量让小的两部分
也就是最后一刀应该切1 3,这样他们总的和最小为4
把4放入arr,继续选择最小的两部分作为最后一刀……
在这里插入图片描述

用小根堆来模拟:
sum=0,结果
(1)将arr全部放入小根堆,让小根堆堆顶2个连续弹出,求和为cur,sum+=cur。
(2)将cur再次放入小根堆,回到(1),不断玩
(3)找到小根堆仅剩下最后的结果cur了,它也就是sum,返回结果
这样相当于每次都把数组中最小的俩数,拿出来做和,这样代价最小
这就是哈夫曼树!!【大厂的笔试中亲眼见过的哦】

手撕代码:

//复习:哈夫曼树,小根堆实现public static int minCostReview(int[] arr){int N = arr.length;PriorityQueue<Integer> heap = new PriorityQueue<>();for (int i = 0; i < N; i++) {heap.add(arr[i]);}//然后模拟哈夫曼树int sum = 0;//结果while (heap.size() != 1){//当最后一次结果加入后,就停止int cur = heap.poll() +heap.poll();//2个连续弹出最小值heap.add(cur);//再次加入heapsum += cur;}return sum;}public static void test(){int[] arr = {10,20,30};//int cost = lessMoeny(arr);System.out.println(cost);cost = minCostReview(arr);System.out.println(cost);}public static void main(String[] args) {test();}

结果:

90
90

总结

提示:重要经验:

1)贪心策略就是多见题,多思考,多总结,培养敏感度!
2)本题的关键在于切一刀要代价最小,那么我们考虑切刀两遍的量尽量平衡,而且越小越好,用哈夫曼树解决,用小根堆模拟。
3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑时间复杂度最优,也要考虑空间复杂度最优。

这篇关于贪心策略:请你最最小的金条分割代价的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

在JS中的设计模式的单例模式、策略模式、代理模式、原型模式浅讲

1. 单例模式(Singleton Pattern) 确保一个类只有一个实例,并提供一个全局访问点。 示例代码: class Singleton {constructor() {if (Singleton.instance) {return Singleton.instance;}Singleton.instance = this;this.data = [];}addData(value)

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若