1.4.24

1.4.24 #

解答 #

第一问：二分查找即可。

第二问：按照第 1, 2, 4, 8,…, 2^k 层顺序查找，一直到 2^k > F，随后在 [2^(k - 1), 2^k] 范围中二分查找。

代码 #

这里建立了一个结构体用于返回测试结果：

internal struct TestResult
{
    public int F; // 找到的 F 值。
    public int BrokenEggs; // 打碎的鸡蛋数。
}

用于测试的方法：

/// <summary>
/// 扔鸡蛋，没碎返回 true，碎了返回 false。
/// </summary>
/// <param name="floor">扔鸡蛋的高度。</param>
/// <returns></returns>
static bool ThrowEgg(int floor)
{
    return floor <= f;
}

/// <summary>
/// 第一种方案。
/// </summary>
/// <param name="a">大楼。</param>
/// <returns></returns>
static TestResult PlanA(int[] a)
{
    var lo = 0;
    var hi = a.Length - 1;
    var eggs = 0;
    var result = new TestResult();

    while (lo <= hi)
    {
        var mid = lo + (hi - lo) / 2;
        if (ThrowEgg(mid))
        {
            lo = mid + 1;
        }
        else
        {
            eggs++;
            hi = mid - 1;
        }
    }

    result.BrokenEggs = eggs;
    result.F = hi;
    return result;
}

/// <summary>
/// 第二种方案。
/// </summary>
/// <param name="a">大楼。</param>
/// <returns></returns>
static TestResult PlanB(int[] a)
{
    var lo = 0;
    var hi = 1;
    var eggs = 0;
    var result = new TestResult();

    while (ThrowEgg(hi))
    {
        lo = hi;
        hi *= 2;
    }

    eggs++;

    if (hi > a.Length - 1)
    {
        hi = a.Length - 1;
    }

    while (lo <= hi)
    {
        var mid = lo + (hi - lo) / 2;
        if (ThrowEgg(mid))
        {
            lo = mid + 1;
        }
        else
        {
            eggs++;
            hi = mid - 1;
        }
    }

    result.BrokenEggs = eggs;
    result.F = hi;
    return result;
}