hihocoder的hiho一下，第256周的题目

---

原题我的解答别人的解答

---

原题

传送门：https://hihocoder.com/contest/hiho256/problem/1

时间限制: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

---

我的解答

每个机器人有两个选择：1.造机器人2.做任务；造一个机器人用时Q,如果总任务数平均到当前机器人，要花的时间超过了2Q，那么这个机器人就应该选择再造一个机器人。

但是，是不是会出现一部分机器人造人，另一部分做任务的情况呢？ 好像这边有这种情况 的 话，总的最短用时还是不变的？ 这里边有点复杂，没想明白，先按都一起复制，复制完了一起加工来看吧。

#include <iostream> #include <cmath> int main(int argc, char** argv) { int n, q; scanf("%d %d", &n, &q); // 首先计算需要复制几次 int k = ceil(log((double)(n/(2*q))) / log(2)); // 再计算用时 int ans = k*q + ceil((double)(n/(pow(2, k)))); printf("%d\n", ans); return 0; }

但是通过情况为WA，60/100 遂改了一下：

int main(int argc, char** argv) { long long int n; int q; scanf("%lld %d", &n, &q); // 首先计算需要复制几次 long long int k = ceil(log((double)(n/(2*q))) / log(2.0)); // 再计算用时 long long int ans = k*q + ceil((double)(n/(pow(2.0, k)))); printf("%lld\n", ans); return 0; }

这次变成80/100了 又改了一下：

int main(int argc, char** argv) { long long int n; int q; scanf("%lld %d", &n, &q); // 首先计算需要复制几次 long long int m=1,k=0; while(n > 2*m*q)//根据结论,机器人应当全部复制 { m *= 2; k++; } // 再计算用时 long long int ans = k*q + ceil((double)(n/(pow(2.0, k)))); printf("%lld\n", ans); return 0; }

---

别人的解答

https://www.cnblogs.com/ECJTUACM-873284962/p/7136061.html 【这里边包括了一部分机器人在复制，其他机器人在工作这种情况不用考虑的相关证明】