题目1 : Robots Crossing River

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

Three kinds of robots want to move from Location A to Location B and then from Location B to Location C by boat.

The only one boat between A and B and only one between B and C. Moving from A to B (and vise versa) takes 2 hours with robots on the boat. Moving from B to C (and vice versa) takes 4 hours. Without robots on the boat the time can be reduced by half. The boat between A and B starts at time 0 moving from A to B. And the other boat starts 2 hours later moving from B to C.

You may assume that embarking and disembarking takes no time for robots.

There are some limits:

  1. Each boat can take 20 robots at most.

  2. On each boat if there are more than 15 robots, no single kind of robots can exceed 50% of the total amount of robots on that boat.

  3. At most 35 robots are allowed to be stranded at B. If a robot goes on his journey to C as soon as he arrives at B he is not considered stranded at B.

Given the number of three kinds robots what is the minimum hours to take them from A to C?

输入

Three integers X, Y and Z denoting the number of the three kinds of robots. (0 ≤ X, Y and Z ≤ 1000)

输出

The minimum hours.

样例输入

40 4 4

样例输出

24

分析

这道题目来源是某北美startup的面试题，看上去比较复杂，可能是为了考察候选人分析问题的能力？

首先需要看出整个流程的瓶颈完全在B-C这一段(B-C段花费时间比较长)，换句话说我们只需求出所有机器人从B到C的最少时间，再加上2小时就是答案。事实上这个时间恰好等于把所有机器人直接从B运到C最少需要的船次x6。

如果没有“一船超过15个机器人则每种机器人不能超过半数”的限制，我们只需要20/船运走即可，最少船次是ceil((X+Y+Z)/20)。

由于有上面的限制，我们需要仔细讨论一下XYZ的相对大小。不妨设X >= Y >= Z，同时我们称三种机器人也为X、Y、Z类。

1、如果X <= Y + Z，那么我们仍然可以20/船运走，同时所有船都没有机器人超过半数。

这种情况最少船次仍然是是ceil((X+Y+Z)/20)。

2、 如果X > Y + Z，这时我们没办法使所有船都载20机器人。但是我们当然希望能尽量派出载20机器人的船。于是有如下贪心策略：

1) 首先尽量10个X类和10个非X类组成一船，派出若干船直到非X类不足10个机器人。
2) 余下若干(不足10个)非X类机器人，配合尽可能多X类机器人组成一船。这里需要讨论余下的非X类机器人有多少个，不妨设为K。如果K不足8个，那么最多配合15-K个X类机器人，组成一船15个机器人；否则可以配合K个X类机器人，组成一船2K个机器人。
3) 最后只剩下若干X类机器人，这些机器人只能15/船派出。

B点最多放35个机器人完全是多余的条件，从A到B后船上的机器人直接转移到第二艘船上，就不认为是滞留的机器人。这个题应该设定了从A到B的船不能到C区。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int X, Y, Z, temp;
    cin >> X >> Y >> Z;
    if(X < Y) temp = X, X = Y, Y = temp;
    if(Y < Z) temp = Y, Y = Z, Z = temp; //确定Z为最小
    if(X < Y) temp = X, X = Y, Y = temp;
    int ans;
    if(X <= Y + Z) ans = ceil((X+Y+Z) / 20.0) * 6;
    else {
        ans = (Y + Z) / 10;
        int K = (Y + Z) % 10;
        X = X - ans * 10;
        if(K < 8) {
            ans++;
            X = X - (15 - K);
        }
        else {
            ans++;
            X -= K;
        }
        ans += ceil(X / 15.0);
        ans *= 6;
    }
    cout << ans << endl;
    return 0;
}