如何定位lilypads for leapfrogs？

Question

我最近一直在练习解决问题的能力,为高中编程竞赛做准备,遇到了一个有趣的问题,真棒青蛙

Frogleaping举办的首届国际奥林匹克运动会将于2013年在澳大利亚举行,您将决心取胜.虽然你想要与这些粘糊糊的,跳跃的生物无关,但你计划进入一个类似青蛙的机器人,你知道它将比所有其他有机进入者更快.

IOF发生在一个大池塘中,其中有一系列百合垫排列成一条长线.比赛的规则很简单:你的青蛙将被放置在第一个百合垫上,然后它必须跳到第二个百合垫,然后是第三个,依此类推,直到它到达最后一个百合垫.请注意,你不能"跳过"百合垫 - 每个睡莲必须跳一次.到达最后一个百合垫的第一只青蛙将赢得比赛.由于您的机器人青蛙具有超级蛙的速度,您对自己的胜利充满信心.

然而,你的青蛙有一个轻微的不正确的缺陷 - 它只能跳一个固定的距离.具体来说,它只能从当前位置向前跳K米,即使它将青蛙落在水中(它会迅速短路).

由于最初的百合垫位置可能使你的青蛙无法到达最后一个百合垫,你打算创造一个分心并移动百合花垫,使它们间隔K米,让你的青蛙从第一个跳到最后没有掉进水里.将百合垫移动一米将花费你一秒钟,你花费越来越多地移动百合垫,IOF评委就越有可能注意到并取消你参加比赛的资格.

鉴于在课程中百合垫之间的初始距离,你必须编写一个程序来计算你必须花费移动百合垫的最短时间,使得所有成对的连续百合垫恰好相距K米.您可以假设池塘足够长,以便第一个百合垫可以向后移动任何距离,并且最后一个百合垫可以向前移动任何距离.

http://orac.amt.edu.au/cgi-bin/train/problem.pl?set=aio12sen&problemid=632上的输入和输出示例

---

我已经考虑过这个漫长而艰难的事情,但考虑到时间限制甚至无视,我仍然无法想到任何完成它的方法.任何有关如何处理此问题的建议或任何有关算法/概念的研究建议都将受到重视.在此先感谢您的帮助.

任何代码都会受到赞赏,最好是c/c ++,python,Java或c#.谢谢

Answer 1

您选择放置第一个睡莲叶的位置完全决定了其他睡莲叶的位置（因为它们都必须相距 K 距离）。对于给定的选择，最便宜的策略显然是 \xe2\x80\x94 保持睡莲的原始顺序（因为任何两个睡莲调换的策略都可以通过不调换它们来改进）。

\n\n

问题是最小化第一个睡莲的结束位置f(i)在哪里i，函数f是从那里开始将所有 N 个睡莲移动到相距 K 的成本。

\n\n

f对给定的计算i速度很快 - 这只是算术（我们从“无换位”观察中推导出每朵百合的结束位置，并将与起始位置的差异相加）。

\n\n

我们可以通过对所有 进行强力搜索来最小化 f i，但这可能会太慢（肯定太慢了，因为这是一场算法竞赛）。所以我们需要更智能地搜索空间。二分查找？不完全是，因为这要求我们知道我们正在寻找什么值，并且 f 是单调的。

\n\n

看起来像什么f？想想这个。

\n\n

函数 f 是凸函数（U 形）。为什么？这是根据我们的“无换位”观察得出的。对于 i 的任何选择，一些百合花需要向右拖动，另一些则需要向左拖动。如果需要向右拖动的百合花多于向左拖动的百合花，那么我们可以通过将起始百合花 i（和其余的）向右移动一步来改进 f（f 将减少差值）。最后，观察需要向右移动的百合花数量是i的减函数，也就是说f\'\' >= 0。我们已经证明f是凸的。

\n\n

现在我们查找或发明（有趣）一种快速的类似二分搜索的算法来最小化一般凸函数，并应用它。或者，更简单的是，我们可以使用沼泽标准二分搜索来求解 f\'(i) = 0，其中 f\' 是需要在每个方向拖动的百合花数量之间的差值。

\n\n\n\n

请记住，在编写任何代码之前先在纸上解决问题。编程会分散我们思考问题的注意力。

\n\n

def solve(startings, K):\n    N = len(startings)\n\n    def ends(start):\n        stop = start + N*K \n        endings = range(start, stop, K)\n        assert len(endings) == N\n        return endings\n\n    def f(start):\n        endings = ends(start)\n        return sum(abs(x-y) for (x,y) in zip(startings, endings))\n\n    def f_prime(start):\n        endings = ends(start)\n        cost = sum(cmp(x,y) for (x,y) in zip(startings, endings))\n        return cost\n\n    lower = min(startings) - N*K\n    upper = max(startings) + N*K\n    g = lambda x: -1 * f_prime(x)\n\n    stationary_point = binary_search(g, lower, upper)\n    i_best = min(stationary_point, stationary_point + 1, key = f)\n    return f(i_best)\n\ndef binary_search(f, lower, upper):\n    """Find the greatest integer n, lower <= n <= upper, such that f(n) <= 0. Assumes f is increasing."""\n    assert upper >= lower\n    assert f(upper) >= f(lower), "f must be increasing"\n    assert f(upper) >= 0 >= f(lower), "f must have a root in range"\n\n    while upper > lower+1:\n        mid = (upper + lower) // 2\n        if f(mid) <= 0:\n            lower = mid\n        else:\n            upper = mid\n\n    return upper if f(upper) <= 0 else lower\n\n# unit tests\nassert binary_search(lambda x: x - 4, 0, 6) == 4\nassert binary_search(lambda x: x**2 - 5, 0, 10) == 2\nassert binary_search(lambda x: x, 0, 6) == 0    \nassert binary_search(lambda x: x-6, 0, 6) == 6\n\nif __name__ == "__main__":\n    import fileinput\n    f = fileinput.input()\n    N, K = [int(x) for x in f.readline().split()]\n    gaps = [int(f.readline()) for i in range(N-1)]\n\n    startings = [0]\n    for gap in gaps:\n        startings.append(startings[-1] + gap)\n    assert len(startings) == N\n\n    print solve(startings, K)\n

\n