实现最快运行时间的算法（问题、解决）

对于算法竞赛训练（不是家庭作业），我们在过去一年中收到了这个问题。将其发布到此站点是因为其他站点需要登录。

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

Image didn't work so posted it here:

它必须在不到一秒的时间内运行，我只能考虑最慢的方法，这就是我尝试过的：

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

我现在正在做的是遍历每个位置，然后遍历该位置的每个有人居住的房屋以找到最大收入位置。

伪代码：

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)，并且对于最大的测试用例不会在一秒内运行。有人可以简单地告诉我如何在最短的运行时间内完成它（除非你愿意，否则不需要代码），因为这已经困扰我很多年了。

编辑：一定有一种方法可以在小于 O(L) 的时间内做到这一点，对吧？

假设列表houses由对组成(x,pop) with 0 <= x < 4*L位置和pop人口。

我们想要最大化的目标函数是

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

朴素算法 O(LN）算法很简单：

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

但完全重新评估是非常浪费的revenue对于每个位置。

为了避免这种情况，请注意这是一个分段线性函数；因此它的导数是分段常数，在两类点处具有不连续性：

• 在家里i，导数变化自slope to slope + 2*population[i]
• 在房子对面的地方i在岛上，导数变化为slope to slope - 2*population[i]

这让事情变得非常简单：

1. 我们只需要检查实际的房屋或对面的房屋，因此复杂性下降到 O(N²).
2. 我们知道如何更新slope从家里i-1去家i，并且只需要 O(1) 时间。
3. 因为我们知道位置 0 处的收入和斜率，并且因为我们知道如何更新slope迭代下去，复杂度实际上下降到 O(N)：在两个连续的房屋/对面的房屋之间，我们只需将坡度乘以距离即可获得收入差异。

所以完整的算法是：

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

为了简单起见，我使用了sorted()合并两种类型的斜率变化，但这不是最佳的，因为它有 O(N log N）复杂性。如果你想要更好的效率，你可以在 O(N) 对与相反的房屋相对应的排序列表进行计时，并将其与 O(N）（例如，使用标准库的heapq.merge）。如果您想最大限度地减少内存使用，您还可以从迭代器而不是列表中进行流式传输。

TLDR：该解决方案实现了最低的可行复杂度 O(N).