2023-09-02 21:09 深圳大学 C++

关注

9.2美团

100 100 6.67 45 100
想问问各位哥第三题怎么写
就是那个要使第一个数最大的最小操作数
例如：
4
1 2 3 4
输出：
2

可对任一元素x2或/2向下取整。
每次笔试遇到这种题目都不会

全部评论

推荐最新楼层

cccwj

门头沟学院 C++

第三题样例很少，很多100%的其实不对。比如1 2 5 这个其实只需要2次，但是看评论的一些方法需要3次。我的思路是，找出最大元素，和次大元素，先把最大元素/2，直到“将”要比次大元素小。在把第一个元素*2直到比次大元素大。再看下此时和最大元素比还需不需要再乘一次2。这个正确性证明：如果此时想让第一个元素少乘一次2，就要让最大和次大都要/2，所以肯定步数会变多。而对于最大元素，其除2向下取整比第一个元素*2要小的多一些，肯定贪心希望最大元素尽量除2（比如1,2,5这种5/2=1肯定比2*2划算）。

2 回复分享

发布于 2023-09-02 21:52 上海

牛客280361716号

哈尔滨工程大学 C++

记录首个元素，排序，如果记录元素不是排序后的倒数第二个直接乘2直到大于，是倒数第二个判断一下最大的除2个数与乘2个数比较

2 回复分享

发布于 2023-09-02 21:15 黑龙江

meteoroad

复旦大学算法工程师

要维护一个堆吧，当然如果图省事情可以直接第一个数乘2，也可以过83

点赞回复分享

发布于 2023-09-03 01:16 广东

你好coder

北京邮电大学 Java

排序数组nums[1, n]，第一个数依次乘2，直到剩余最后一个数，最后一个数除以2

点赞回复分享

发布于 2023-09-02 22:14 北京

想要睡到自然醒

淘天集团_Java开发

把第一个数提出来剩下的找出最大的那个数循环/2，每除一次结果加一，直到比第一个数小或者相等。通过100

点赞回复分享

发布于 2023-09-02 22:10 浙江

TheFeng

门头沟学院 Java

把第一个数字拿出来，剩下的从小到大排序，并遍历i=1->n-1，如果第一个数字小于当前的a[i]，则让第一个数字*=2知道大于等于；如果大于直接跳过。最后若是走到n-1的位置，则判断a[n-1]/=2所需的步数，和a[0]*=2的步数（直到a[0]>a[n-1]）的最小值，用最小值更新一下答案。这样一来1 2 5的例子，一开始1会和2比大小，然后a[0]变成2，然后和5比大小，发现5/=2比1*2*2要用的次数少，所以最后的答案就是2. 当时这样考虑贪心是因为，如果你当前的a[0]没和最后一位数字比大小，那么不需要让最后的a[n-1]除以2，因为前面还有很多没比过大小的n-2,n-3等等的位置，这些位置如果你想执行除以2的操作，那实际上肯定不如a[0]*=2的操作快。所以真正要比较的只有a[0]和a[n-1]

点赞回复分享

发布于 2023-09-02 22:06 北京

__OWo__

佛光大学 C++

我用的最大堆，每次要么第一个翻倍，要么减半最大值再比较，每一步都贪婪取最大缩短差距的那个方案（维护一个 max-min的差值变量）；

点赞回复分享

发布于 2023-09-02 21:45 四川

LeeX852

重庆邮电大学游戏后端

第三题我是这么做的，先把除第一个数以外的数字升序排序，然后分两个方向计算，一个从左往右，一个从右往左。第一种只需要计算第一个数字跟最后一个数字差了几倍就可以了，连续乘2直到大于等于最后一个数字，乘的次数就是从左往右的结果。然后再从右往左，先从最后一个数字开始，所有大于第一个数的数字都连续除以2直到小于等于第一个数字，所有除以二的次数加起来就是从右往左的计算结果，最后两种方向的结果取最小值就是答案。

点赞回复分享

发布于 2023-09-02 21:30 重庆

喜欢吃火锅的河老师想当offer收割机

湖南大学 C++

大佬，问下第二题怎么做的，我只过了90多😭😭

点赞回复分享

发布于 2023-09-02 21:27 湖南

牛客673209701号

门头沟学院 Java

先遍历找到最大数，然后只要第一个数还大于最大数就判断，如果最大数mod2余1，那就最大数除2，要不然就第一个数乘2，这样直到第一个数大于最大数，退出循环，返回操作的个数结果就行

点赞回复分享

发布于 2023-09-02 21:23 广东

牛客116121086号

北京邮电大学大数据开发工程师

就只有一种情况，全数组只有个数大于第一个数，并且这个数%2=1。这种情况用这个数/2会比直接乘2第一个数少一次

点赞回复分享

发布于 2023-09-02 21:22 山东

要发财的高级磨洋工很伟大

门头沟学院 Java

把除了第一个数都放进优先队列，每次取出比较一下然后除2放回

点赞回复分享

发布于 2023-09-02 21:21 广东

快支棱起来的闭门羹烹饪师很讲道理

东南大学语音/视频/图形开发

找到最大数，往下取整除不就行了

点赞回复分享

发布于 2023-09-02 21:14 广东

神奇的姜呆呆

东北大学算法工程师

第三题写了个dp通过了85%

点赞回复分享

发布于 2023-09-02 21:12 辽宁

xdxd123

武汉晴川学院 C++

正难则反，你只需要枚举需要增加多少次。这个增加显然只会对a[1] 增加，然后判断剩下的元素需要减少多少次。这样复杂度就是( log(1e9) * N)。

点赞回复分享

发布于 2023-09-02 21:11 浙江

laochonger

北京邮电大学 Java

猜了一个首位不是前二就乘法，否则除法，过了…

点赞回复分享

发布于 2023-09-02 21:11 北京

昨天 12:35

已编辑

门头沟学院客户端其它

不是，这我怎么回答啊

谈谈你的优缺点。为什么选择我们公司。为什么实习没转正或者为什么实习转正没留在那家公司。具体原因如下：1.优点和缺点这个事。优点就不用说了，夸自己肯定都会，那老缺点，谁能说自己喜欢钱多事少的工作，无非就是说一些不痛不痒的缺点。来一段我的场面话公式回答：关于我自己的优点，我认为我是一个“勤奋好学”的人 + 具体事情举证，同时也具备“一定的抗压”能力 + 具体事情举证，优点不要墨迹太多，喋喋不休的招人烦 。缺点这方面，说一点就行了，比如：你做事比较急躁、在任务很急的情况下，你会在没有充分思考的情况下就作出决定，紧接着你要说一下这个缺点的好处，然后解释你现在已经不这样了。总之回答这个问题记住一点：“优...

你最讨厌面试问你什么？

点赞评论收藏

不愿透露姓名的神秘牛友

07-24 13:39

我错了我有罪我不该说实话的

在记录秋招的大魔王很...：别被忽悠了，我做了多年销售。我可以告诉你，这就是忽悠你的，销售一定要看底薪也要看提成两者不可缺一。提成是有业绩的时候才拿的到的，谁能保证一直有单状态都好。销售有时候很讲究运气的。底薪是你这个人这个岗位日常工作体现的价值。别小看底薪，你看那些跳槽去做经理主管的，底薪底一些，人家愿意去吗？所以那些说销售靠提成的纯属忽悠，除非他们的业务很容易成单。

点赞评论收藏