首页 > 试题广场 >

质检员的烦恼

[编程题]质检员的烦恼
  • 热度指数:138 时间限制: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
并不是组越少时间就一定越少哦。 一方面,组数少意味着每组的手机数量可能较多。虽然称重的组数少了,但是每组的手机数量多,移动这些手机所花费的时间可能会增加。 另一方面,如果组数过多,虽然每组手机数量少使得移动时间减少,但称重的组数增加,称重时间也会相应增加。 所以需要综合考虑手机数量、单台手机移动时间、每组称重时间以及分组数之间的关系,通过遍历不同的分组数来找到使得总时间最短的分组方式。不能简单地认为组越少时间就一定少。
发表于 2024-10-18 14:34:05 回复(0)