首页 > 试题广场 >

质检员的烦恼

[编程题]质检员的烦恼
  • 热度指数：150 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
每一款vivoX80的手机质量必须控制在无误差的203克。
假设，质检员小V需要从N台X80手机中选出一台质量为204克的不合格手机。

质检员挑选不合格手机的步骤如下：
1、分组：质检员每轮选择一个正整数，假设当前选择的正整数为K，那么将当前未排除嫌疑的手机进行每组K个的分组，如果不能整除K，那么将最后剩余的手机再单独分一组。
2、称重，以步骤1中的每组为单位，称重设备将对每组都进行一次总质量称重。称重完成后，根据计算你就可以确定不合格手机位于哪一组中。
3、排除掉合格的手机组，循环1、2两步骤，直到嫌疑手机仅剩一台。

总花费时间为每一轮花费的时间总和，每一轮的花费时间由以下两部分组成：
a、每台手机都需要移动到称重设备处，假定该轮共X台手机，题目给定单台手机的移动时间A，那么该轮次的移动时间为 X乘以A。
b、称重需要时间，每一组都需要称重，假定当前轮次共被分成了G组，题目给定每组称重的时间B，那么该轮次的称重时间为G乘以B。

现在给定手机的个数N，单台手机移动到称重处的时间A，每组称重需要的时间B。
请帮质检员计算，每轮应该怎样选择正整数K，才能在运气最差的情况下用最短的时间找到不合格的手机？题目要求你输出该最短的时间。
我们假定运气最差的语义为：每一轮都是数量最多的组进入了下一轮。
示例1

输入

22,1,3

输出

56

说明

第一轮共22个手机，那么该轮次移动时间为22*1，我们取该轮次的K值为4，那么组数为6(前5组每组4个，最后一组2个)，称重时间为6*3。
第一轮称重完成后，6组中必然某一组进入下一轮。因为题目要求是运气最差场景，故我们认为前5组中某一组共4台手机进入了下一轮。
第二轮共4台手机，那么该轮移动时间为4*1，我们取第二轮的K值为1，那么组数为4，称重时间为4*3。
第二轮称重完成后，便可以确定问题手机，算法结束。
该方案总时间为56。
无法找到其他短于该时间的值。

备注:
1 <= N <= 10^8
1 <= A <= 10^6
1 <= B <= 10^6
算法知识视频讲解
添加回答
Python
想减肥的00后说我这儿没问题啊头像 想减肥的00后说我这儿没问题啊 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算质检员每轮应该如何选择正整数K，才能在运气最差的情况下用最短的时间找到不合格的手机？并输出该最短的时间。
# @param n int整型 手机个数N
# @param a int整型 单个移动时间A
# @param b int整型 单组称重时间B
# @return long长整型
#
import math
from functools import lru_cache
class Solution:
    def minTime(self , n: int, a: int, b: int) -> int:
        @lru_cache(maxsize=None)
        def f(x, a, b):
            if x == 1:
                return (a + b)
            min_val = (a + b) * x
            count = 0
            for k in range(2, x):
                current = a * x + b * k + f(math.ceil(x / k), a, b)
                if min_val-current > 0:
                    min_val = current
                    count = 0
                else:
                    count += 1
                    if count == 150:
                        break
            return min_val

        return f(n, a, b)
使用最优化方法

发表于 2025-09-11 20:20:39 回复(0)
Python
活泼的河老师被普调头像 活泼的河老师被普调 
from functools import cache
import math
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算质检员每轮应该如何选择正整数K，才能在运气最差的情况下用最短的时间找到不合格的手机？并输出该最短的时间。
# @param n int整型 手机个数N
# @param a int整型 单个移动时间A
# @param b int整型 单组称重时间B
# @return long长整型
#
class Solution:
    @cache
    def minTime(self , n: int, a: int, b: int) -> int:
        if n==1: return 0
        mintime = n*b
        middleK = int(math.sqrt(b*n/(a+b)))
        for k in range(middleK-2*int(math.sqrt(n)), middleK+2*int(math.sqrt(n))):
            if k < 1&nbs***bsp;k > n-1: continue
            if n % k: mintime = min(mintime, (n//k+1)*b+self.minTime(k, a, b))
            else: mintime = min(mintime, n//k*b+self.minTime(k, a, b))
        return mintime+n*a
一种近似解方法，并非合理答案，但是能过hhhh
发表于 2025-09-09 15:38:41 回复(0)
一笑而过2222头像 一笑而过2222
并不是组越少时间就一定越少哦。 一方面，组数少意味着每组的手机数量可能较多。虽然称重的组数少了，但是每组的手机数量多，移动这些手机所花费的时间可能会增加。 另一方面，如果组数过多，虽然每组手机数量少使得移动时间减少，但称重的组数增加，称重时间也会相应增加。 所以需要综合考虑手机数量、单台手机移动时间、每组称重时间以及分组数之间的关系，通过遍历不同的分组数来找到使得总时间最短的分组方式。不能简单地认为组越少时间就一定少。
发表于 2024-10-18 14:34:05 回复(0)
提交观点

问题信息

难度：
3条回答 731浏览

热门推荐

相关试题

质检员的烦恼

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号