骨骼 新鲜 电面

laobai2024 发表于 2020-6-23 15:49
可以通分的把
k/1  + k/2 + k/4 = M

但是这个通分真的做得到吗。。。？这一题数字好比较凑巧。一般的情况，通分怎么做。。。？万一是1e5个最大公约数为1的数，通分后的分母计算机都表示不出来。

二分法我觉得范围是从1到M*max（num）吧，最大值就是全部让最慢的那个机器做最多要多少分钟，然后给一个mid值比如八分钟，看八分钟这些机器一起做一共能做多少产品，如果大于等于m就缩小右边界

djmiss 发表于 2020-6-23 10:10
如果误差精度允许的话，是不是可以用数学办法：
一个单位时间能做的个数：sum = 1/a[0] + 1/a[1] + ... +  ...

数学解不可行吧，比如list是 [1,2,2]，那1分钟就两个，但其实才完成一个....

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

laobai2024 发表于 2020-6-23 15:49
可以通分的把
k/1  + k/2 + k/4 = M

还真是！初中数学，我感觉也忘了

sindy29 发表于 2020-6-23 20:11
数学解不可行吧，比如list是 [1,2,2]，那1分钟就两个，但其实才完成一个....

说得对，数学不行，通分也不行

AlbertZhong 发表于 2020-6-23 16:47
二分。。。。
令函数f(x)=给定x分钟总共可以完成多少商品，显然f(x)单调增
每次猜一个数x，然后看是否满 ...

对于每个X ， 都要遍历每台机器，看在X 分钟能生产多少个 然后加总，是这样吗

workworkhard 发表于 2020-7-6 13:28
对于每个X ， 都要遍历每台机器，看在X 分钟能生产多少个 然后加总，是这样吗

是的。这就是O(nlogn)里第一个n的来源（当然第二个log里面的部分可能更大。。。通常是和值域有关的）