算法（概率。解决）实现最快的运行时间 [英] Algorithm (prob. solving) achieving fastest runtime

问题描述

有关的算法竞赛培训（不做作业），我们得到从过去的一年里这个问题。贴吧到这个网站，因为其他网站需要登录。

For an algorithm competition training (not homework) we were given this question from a past year. Posted it to this site because the other site required a login.

这就是问题所在： http://pastehtml.com/view/c5nhqhdcw.html

图片没有工作，所以贴在这里：

Image didn't work so posted it here:

它在不到一秒钟的运行，我只能想到这样做了最慢的方式，这是我的尝试：

It has to run in less than one second and I can only think about the slowest way to do it, this is what I tried:

with open('islandin.txt') as fin:
    num_houses, length = map(int, fin.readline().split())
    tot_length = length * 4 # side length of square
    houses = [map(int, line.split()) for line in fin] # inhabited houses read into list from text file

def cost(house_no):
    money = 0
    for h, p in houses:
        if h == house_no: # Skip this house since you don't count the one you build on
            continue
        d = abs(h - house_no)
        shortest_dist = min(d, tot_length - d)    
        money += shortest_dist * p
    return money


def paths():
    for house_no in xrange(1, length * 4 + 1):
        yield house_no, cost(house_no)
        print house_no, cost(house_no) # for testing

print max(paths(), key=lambda (h, m): m) # Gets max path based on the money it makes

我在做什么，此刻正在经历的每个位置，然后经过每个有人居住的房子的位置，找到最大收益的位置。

What I'm doing at the moment is going through each location and then going through each inhabited house for that location to find the max income location.

伪code：

max_money = 0
max_location = 0
for every location in 1 to length * 4 + 1
    money = 0
    for house in inhabited_houses:
        money = money + shortest_dist * num_people_in_this_house
    if money > max_money
        max_money = money
        max_location = location

这是太慢了，因为它是O（LN），并在第二的最大测试用例不会运行研究。是否有人可以简单地告诉我怎么做，在最短的运行时间（除非你想code不要求），因为这已被窃听我的年龄。

This is too slow since it's O(LN) and won't run in under a second for the largest test case. Can someone please simply tell me how to do it in the shortest run time (code isn't required unless you want to) since this has been bugging me for ages.

编辑：？必须有这样做的方式小于O（L）右

There must be a way of doing this in less than O(L) right?

推荐答案

假设列表房子是由对（X，流行）与 0℃= X＆LT; 4 * L 位置和流行人口。

Suppose the list houses is composed of pairs (x,pop) with 0 <= x < 4*L the location and pop the population.

的目标函数，这是我们希望最大化，是

The objective function, which we want to maximize, is

def revenue(i):
    return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

天真的算法O（ LN 的）的算法很简单：

The naive algorithm O(LN) algorithm is simply:

max_revenue = max(revenue(i) for i in range(4*L))

不过，这是令人难以置信的浪费完全重新评估收入的每个位置。

要避免这种情况，注意到这是一个分段线性函数;所以它的衍生物是分段恒定的，不连续的2种点：

To avoid that, notice that this is a piecewise-linear function; so its derivative is piecewise constant, with discontinuities at two kinds of points:

• 在家里我，从斜率到坡衍生变化+ 2 *人口[我]
• 在位于点对面的房子我岛上，从斜率到<$ C $的衍生变化C>坡 - 2 *人口[I]

• at house i, the derivative changes from slope to slope + 2*population[i]
• at the point located opposite house i on the island, the derivative changes from slope to slope - 2*population[i]

这使事情变得非常简单：

This makes things very simple:

1. 我们只需要考察实际的房子对面，房子的还是，所以复杂度降低到O（ N 的²）。
2. 我们知道如何更新斜率从房子 I-1 来的房子我，它只需要O（1）时间。
3. 既然我们知道收入和斜率的地址0，因为我们知道如何更新斜率反复，复杂性实际上下降到O（ñ 的）：连续两个房子之间/相反，房子的，我们可以只用距离乘以斜率来获得收入的差异

1. We only have to examine actual houses or opposite-of-houses, so the complexity drops to O(N²).
2. We know how to update the slope from house i-1 to house i, and it requires only O(1) time.
3. Since we know the revenue and the slope at location 0, and since we know how to update the slope iteratively, the complexity actually drops to O(N): between two consecutive houses/opposite-of-houses, we can just multiply the slope by the distance to obtain the difference in revenue.

所以，完整的算法是：

def algorithm(houses, L):
    def revenue(i):
        return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

    slope_changes = sorted(
            [(x, 2*pop) for x,pop in houses] +
            [((x+2*L)%(4*L), -2*pop) for x,pop in houses])

    current_x = 0
    current_revenue = revenue(0)
    current_slope = current_revenue - revenue(4*L-1)
    best_revenue = current_revenue

    for x, slope_delta in slope_changes:
        current_revenue += (x-current_x) * current_slope
        current_slope += slope_delta
        current_x = x
        best_revenue = max(best_revenue, current_revenue)

    return best_revenue

为了简单起见，我用排序（）合并两种类型的坡度变化，但这不是最佳的，因为它有O（ N 日志的 N 的）复杂性。如果你想更好的效率，你可以在O产生（的 N 的）时间相对应的，相反，房子排序列表，并与房屋列表合并其在O（ N ）（例如，使用标准库的 heapq.merge ）。你也可以从迭代器，而非列表流，如果你想减少内存使用。

To keep things simple I used sorted() to merge the two types of slope changes, but this is not optimal as it has O(N log N) complexity. If you want better efficiency, you can generate in O(N) time a sorted list corresponding to the opposite-of-houses, and merge it with the list of houses in O(N) (e.g. with the standard library's heapq.merge). You could also stream from iterators instead of lists if you want to minimize memory usage.

TLDR：该解决方案实现了邻可行的最低复杂性（的 N 的）

TLDR: this solution achieves the lowest feasible complexity of O(N).

这篇关于算法（概率。解决）实现最快的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！