#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

样例输出

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

思路分析

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

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

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

下面给出AC代码：

 #include <bits/stdc++.h>

 typedef long long ll;

 using namespace std;

 int main()

 {

     ll n,q;

     cin>>n>>q;//n表示任务总数,q表示生产一次机器人需要的时间

     ll m=,r=;//m表示初始时机器人的数量,r表示生产次数

     while(n>*m*q)//根据结论,机器人应当全部复制

     {

         m<<=;//倍增操作

         r++;

     }

     ll t=q*r+n/m;//总时间为生产机器人所花费的时间q*r+任务数与机器人的比值(每个机器人单位时间生产单位价值的产品)

     if(n%m)//不能整除的话说明t++;

         t++;

     cout<<t<<endl;

     return ;

 }

巴特西

hihoCoder #1498 : Diligent Robots【数学】

#1498 : Diligent Robots

描述

输入

输出

思路分析

下面给出AC代码：

最新文章

热门文章