【每日算法Day 102】美团 AI 平台算法工程师面试编程题

您所在的位置:网站首页 美团算法面试题 【每日算法Day 102】美团 AI 平台算法工程师面试编程题

【每日算法Day 102】美团 AI 平台算法工程师面试编程题

2024-07-09 19:13| 来源: 网络整理| 查看: 265

今天去尝试了一下美团 AI 平台,两次面试连一起。但是两位面试官小哥都是做推荐的,我们互相都不了解对方怎么做的。于是乎就做算法题,讲论文(把不懂的人讲懂确实困难),然后全程小哥给我介绍他们部门情况,我就挂机听着。不管这家拿不拿得到,就当刷刷经验吧,也挺不错的。一共三道题目,前两道一个最长上升子序列,一道快速排序,就不讲了,都是原题。 题目描述

题目链接: 牛客网:分石子[1]

牛牛有 n 堆石子堆,第 i 堆一共有 a[i] 个石子。

牛牛可以对任意一堆石子数量大于 1 的石子堆进行分裂操作,分裂成两堆新的石子数量都大于等于 1 的石子堆。

现在牛牛需要通过分裂得到 m 堆石子,他想知道这 m 堆石子的最小值最大可以是多少?

示例:

输入: 3,5,[3,5,6] 输出: 2 解释: 把5分裂成2和3 把6分裂成2和4 得到五堆石子[3,2,3,2,4]

备注:

1 \le n \le 10^5, n \le m \le \sum{a_i}, 1 \le a_i \le 10^9第一个参数 n 代表石子堆的个数第二个参数 m 表示需要得到的石子堆数。第三个参数 vector a 代表每堆石子堆的石子个数 题解

一拿到这个题目,就看出来这是一道二分答案的题目。

首先定义上下界 l = 1, r = min{a[i]} ,也就是说,每一堆个数最小值至少为 1 ,最多就是初始的时候最小的那堆个数。

然后对于 mid = (l + r) / 2 ,含义就是假设最终最小的那堆有 mid 个。我们求出初始时每一堆最多可以划分出多少个数全部大于等于 mid 的子堆,显然个数是 a[i] / mid 取整,记总堆数为 cnt。

如果 cnt < m ,那么说明 mid 太大了,你最多也不可能划分成 m 堆,所以更新 r = mid - 1 。如果 cnt > m ,那么说明 mid 太小了,你能划分的堆数大于了 m ,那么更新 l = mid + 1 。最后如果 cnt = m ,你就暂存一下答案,因为这时的 mid 是有可能成为最终答案的。但是 mid 还是可能太小了,因为 mid 稍微大一点 cnt 是不会变的,所以继续更新 l = mid + 1 。

最终返回暂存的答案 res 即可。注意这题的二分框架和之前做过的有所不同,在等号判断上得特别小心,我一开始没想清楚,错了好多次才通过的。

代码 class Solution { public: /** * 分石子 * @param n int整型 * @param m long长整型 * @param a int整型vector * @return int整型 */ int solve(int n, long long m, vector& a) { typedef long long ll; ll l = 1, r = *min_element(a.begin(), a.end()), res = 0; while (l


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3