【问题】微软第二题

数据规模多少？显然如果要复制机器人肯定要在一开始就复制，小的话直接枚举机器人的数量。。大的话算个数量的公式搞一搞

求导？ 发自「贵邮」

给定N和Q...数据规模就是N啊，可大可小 【 在 LXYXYNT 的大作中提到: 】 : 数据规模多少？显然如果要复制机器人肯定要在一开始就复制，小的话直接枚举机器人的数量。。大的话算个数量的公式搞一搞 : 发自「贵邮」

能详细说说吗，lz太渣理解不了= =！ 【 在 mynotwo 的大作中提到: 】 : 求导？ : : 发自「贵邮」 : 发自「贵邮」

只是这样想的…… 假设有A个机器人，那么产生机器人的时间需要log2(A)*Q，总的时间就是log2(A)*Q+N/A,然后这个方程存在一个最小值吧……再对这个方程进行求导=0……我也是个渣以上都是我随口的胡说八道…… 【 在 liuyehcf 的大作中提到: 】 : 能详细说说吗，lz太渣理解不了= =！ : : 发自「贵邮」

是这样的。因为刚开始只有一个机器人，生产一个机器人的时间成本是q，生产一个机器人的收益是n/2，如果收益大于成本，那就生产机器人。第二次，有两个机器人，这两个机器人都要生产机器人，生产机器人的成本还是q，生产机器人的收益是（n/2）/2，如果收益大于成本，就生产。 给你一个通过100%的代码，你看看： public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); long q = sc.nextLong(); float robot = 1; float gain = n; long time = 0; while (gain / 2 > q) { robot = robot * 2; gain = gain / 2; time += 1; } double left = Math.ceil(n / robot); long result = (long) (time * q + left); System.out.println(result); sc.close(); } 样例是输入10 1输出5 如果是一个机器人，不生产机器人，那么需要时间10。如果生产一个机器人，然后两个机器人一起生产，那就需要1+10/2个时间。。。。。。下面罗列了对应表 最终机器人数量：1 ->2->4->8->16->32 需要最短时间： 10->6->5->5->5->6 可以看出总时间会随着机器人的繁殖，先减少后增大。这是因为机器人过度繁殖会使生产机器人的收益减少。当收益为负时，时间就会增加，这个不难理解吧。 根据题意，另一个样例： 输入10 2输出7 1 ->2->4->8->16 10->7->7->8->9 有人会问，如果让有的机器人生产机器人，有的机器人不生产机器人，这种情况怎么办？这时可以考虑所有机器人都生产机器人，所有机器人都不生产机器人，这两种情况。那么上述情况介于后面所说的两种情况。其总时间也介于两者之间。那么这种情况就不会是最优解，一定是后两种情况中的一种是最优解。 不知道楼主有没有理解？

非常感谢！~整体思路明白了，但是有一个细节还不太理解，为什么生产一个机器人的时间收益是n/2 1个机器人做完n个job，需要n小时，如果复制，花费q小时，还剩n-q小时能做job，那么(n-q)*2>=n*1是有收益的 即n/2>=q是有收益的，是这样理解么 【 在 liuquanwea 的大作中提到: 】 : 是这样的。因为刚开始只有一个机器人，生产一个机器人的时间成本是q，生产一个机器人的收益是n/2，如果收益大于成本，那就生产机器人。第二次，有两个机器人，这两个机器人都要生产机器人，生产机器人的成本还是q，生产机器人的收益是（n/2）/2，如果收益大于成本，就生产。 : 给你一个通过100%的代码，你看看： : public static void main(String[] args) { : ...................

谢谢，能理解了，结合6楼，这个A一定是2的幂次，即机器人要么全部复制，要么全部开始工作 【 在 mynotwo 的大作中提到: 】 : 只是这样想的…… : 假设有A个机器人，那么产生机器人的时间需要log2(A)*Q，总的时间就是log2(A)*Q+N/A,然后这个方程存在一个最小值吧……再对这个方程进行求导=0……我也是个渣以上都是我随口的胡说八道……

第一次复制需要消耗Q时间，而复制一次会节省一半的时间，即N/2的时间，节省的时间比消耗的多就算有收益；第二次还是消耗Q，比之前又节省一半，所以是N/4，是不是可以这样理解？