专栏首页小樱的经验随笔hihoCoder #1498 : Diligent Robots【数学】

hihoCoder #1498 : Diligent Robots【数学】

#1498 : Diligent Robots

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

There are N jobs to be finished. It takes a robot 1 hour to finish one job.

At the beginning you have only one robot. Luckily a robot may build more robots identical to itself. It takes a robot Q hours to build another robot.  

So what is the minimum number of hours to finish N jobs?

Note two or more robots working on the same job or building the same robot won't accelerate the progress.

输入

The first line contains 2 integers, N and Q.  

For 70% of the data, 1 <= N <= 1000000  

For 100% of the data, 1 <= N <= 1000000000000, 1 <= Q <= 1000

输出

The minimum number of hours.

样例输入

10 1

样例输出

5

题目链接:https://hihocoder.com/problemset/problem/1498

思路分析

首先,如果要复制机器,就要尽早复制,因为尽早复制可以尽早投入生产。 我的纠结点在于,复制的最后一轮,会不会有一部分机器人在复制,其他机器人在工作? 通过严谨的证明说明是不会的。

以下证明过程参考一位大神的,很严谨的证明,I love it!QAQ

因为我上面的证明里得到了“T>2qm”这个临界条件,因此在代码里可以直接使用。详解代码中已给出!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 int main()
 5 {
 6     ll n,q;
 7     cin>>n>>q;//n表示任务总数,q表示生产一次机器人需要的时间
 8     ll m=1,r=0;//m表示初始时机器人的数量,r表示生产次数
 9     while(n>2*m*q)//根据结论,机器人应当全部复制
10     {
11         m<<=1;//倍增操作
12         r++;
13     }
14     ll t=q*r+n/m;//总时间为生产机器人所花费的时间q*r+任务数与机器人的比值(每个机器人单位时间生产单位价值的产品)
15     if(n%m)//不能整除的话说明t++;
16         t++;
17     cout<<t<<endl;
18     return 0;
19 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ 2209 The King(简单贪心)

    The King Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7499...

    Angel_Kitty
  • POJ 1017 Packets

    Packets Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 53812...

    Angel_Kitty
  • 【批处理学习笔记】第三课:简单批处理命令(2)

    cls 命令     清除屏幕。执行该命令后,屏幕上的所有信息都被清除,光标重新定位至屏幕左上角。 REM 和 :: REM为注释命令,一般用来给程序加上注...

    Angel_Kitty
  • oracle 常用command

    Lunatic 整理 1. 删除表的注意事项 在删除一个表中的全部数据时,须使用TRUNCATE TABLE 表名;因为用DROP TABLE,DE...

    阿新
  • 移动机器人中的现代控制理论之状态空间表达式

    https://zhangrelay.blog.csdn.net/article/category/6161998

    zhangrelay
  • kubernetes之StatefulSet

    k8s的statefulset在1.5之后才引入的,1.5之前用的是petset,关于petset在之前的老版本的paas开发中用的就是petset,petse...

    菲宇
  • 近实时计算曲面区域标签(Human-Computer Interaction)

    在标记区域中的一个问题就出现在放置一个地理区域的标签之后。给定区域的外边界和一组可选的孔。我们的目标是找到一个标签位置,使标签跨越该区域,并符合其形状。

    用户6869393
  • 改善深层神经网络 - 第二课第三周作业 TensorFlow Tutorial

    Welcome to this week’s programming assignment. Until now, you’ve always used num...

    Steve Wang
  • poj-1005-l tanink i need a houseboat

    Fred Mapper is considering purchasing some land in Louisiana to build his house ...

    瑾诺学长
  • 动态 | 百度发布 Paddle Fluid v1.3 版本,带来多项重要更新

    AI 科技评论按:日前,百度 PaddlePaddle 更新至 Fluid v1.3 版本,一如既往地, Fluid v1.3 版本在基础框架、预测引擎、模型建...

    AI科技评论

扫码关注云+社区

领取腾讯云代金券