这是一个在数学上不太倾斜的解决方案，适用于O(n).
让我们将房屋（索引从 0 开始）划分为两个不相交的集合：
F，“前”，人们从 CCW 走到房子的地方B，“回”，人们沿着 CW 走到房子的地方
和一个单独的房子p，标志着工厂将建造的当前位置。
我的插图基于图像中给出的示例。
按照惯例，让我们将一半的房子分配给F，而正好少分配一个给B。
借助简单的模运算，我们可以轻松访问房屋，(p + offset) % 12这要归功于 Python 对模运算符的理智实现，这与其他一些 流行的语言完全不同。
如果我们任意选择一个位置p，我们可以很容易地确定耗水量O(L)。
我们可以再次执行此操作，p以获得O(L^2).
但是，如果我们只移动p一个位置，我们可以O(1)通过稍微巧妙的观察来确定新的消费：当我们设置 时，居住在F（或B分别）的人数决定了消费的F变化量p' = p+1。（以及一些更正，因为F它本身会改变）。我已经尽我所能在这里描绘了这一点。
我们最终的总运行时间为O(L).
该算法的程序在帖子的末尾。
但我们可以做得更好。只要集合之间没有房屋变化，相加的cs 和ws 将为零。我们可以计算出这些步骤有多少，并一步完成。
房屋在以下情况下换组： - 何时p在房屋上 - 何时在房屋p对面
在下图中，我已经可视化了算法现在为更新Cs 和Ws 所做的停止。突出显示的是导致算法停止的房子。
该算法从一所房子开始（或与之相反，我们稍后会看到原因），在这种情况下恰好是一所房子。
同样，我们既有消费C(B) = 3*1又有C(F) = 2 * 1. 如果我们p向右移动 1，我们将添加4和C(B)减去1。C(F)如果我们p再次移动，就会发生完全相同的事情。
只要相同的两组房屋分别靠近和远离，Cs的变化是恒定的。
我们现在稍微改变一下定义B：它现在也包含p! （这不会改变上述关于算法优化版本的段落）。
这样做是因为当我们移动到下一步时，我们将增加重复移动的房屋的重量。当前位置的房子p向右移动时正在移动，因此W(B)是正确的加法。
另一种情况是当房子停止移动并再次靠近时。在这种情况下，Cs 会发生巨大变化，因为6*weight从一个C到另一个。那是我们需要停止的另一种情况。
我希望很清楚它是如何以及为什么起作用的，所以我将把工作算法留在这里。请询问是否有不清楚的地方。
上）：
import itertools
def hippo_island(houses, L):
return PlantBuilder(houses, L).solution
class PlantBuilder:
def __init__(self, houses, L):
self.L = L
self.houses = sorted(houses)
self.changes = sorted(
[((pos + L /2) % L, -transfer) for pos, transfer in self.houses] +
self.houses)
self.starting_position = min(self.changes)[0]
def is_front(pos_population):
pos = pos_population[0]
pos += L if pos < self.starting_position else 0
return self.starting_position < pos <= self.starting_position + L // 2
front_houses = filter(is_front, self.houses)
back_houses = list(itertools.ifilterfalse(is_front, self.houses))
self.front_count = len(houses) // 2
self.back_count = len(houses) - self.front_count - 1
(self.back_weight, self.back_consumption) = self._initialize_back(back_houses)
(self.front_weight, self.front_consumption) = self._initialize_front(front_houses)
self.solution = (0, self.back_weight + self.front_weight)
self.run()
def distance(self, i, j):
return min((i - j) % self.L, self.L - (i - j) % self.L)
def run(self):
for (position, weight) in self.consumptions():
self.update_solution(position, weight)
def consumptions(self):
last_position = self.starting_position
for position, transfer in self.changes[1:]:
distance = position - last_position
self.front_consumption -= distance * self.front_weight
self.front_consumption += distance * self.back_weight
self.back_weight += transfer
self.front_weight -= transfer
# We are opposite of a house, it will change from B to F
if transfer < 0:
self.front_consumption -= self.L/2 * transfer
self.front_consumption += self.L/2 * transfer
last_position = position
yield (position, self.back_consumption + self.front_consumption)
def update_solution(self, position, weight):
(best_position, best_weight) = self.solution
if weight > best_weight:
self.solution = (position, weight)
def _initialize_front(self, front_houses):
weight = 0
consumption = 0
for position, population in front_houses:
distance = self.distance(self.starting_position, position)
consumption += distance * population
weight += population
return (weight, consumption)
def _initialize_back(self, back_houses):
weight = back_houses[0][1]
consumption = 0
for position, population in back_houses[1:]:
distance = self.distance(self.starting_position, position)
consumption += distance * population
weight += population
return (weight, consumption)
O(L)
def hippo_island(houses):
return PlantBuilder(houses).solution
class PlantBuilder:
def __init__(self, houses):
self.houses = houses
self.front_count = len(houses) // 2
self.back_count = len(houses) - self.front_count - 1
(self.back_weight, self.back_consumption) = self.initialize_back()
(self.front_weight, self.front_consumption) = self.initialize_front()
self.solution = (0, self.back_weight + self.front_weight)
self.run()
def run(self):
for (position, weight) in self.consumptions():
self.update_solution(position, weight)
def consumptions(self):
for position in range(1, len(self.houses)):
self.remove_current_position_from_front(position)
self.add_house_furthest_from_back_to_front(position)
self.remove_furthest_house_from_back(position)
self.add_house_at_last_position_to_back(position)
yield (position, self.back_consumption + self.front_consumption)
def add_house_at_last_position_to_back(self, position):
self.back_weight += self.houses[position - 1]
self.back_consumption += self.back_weight
def remove_furthest_house_from_back(self, position):
house_position = position - self.back_count - 1
distance = self.back_count
self.back_weight -= self.houses[house_position]
self.back_consumption -= distance * self.houses[house_position]
def add_house_furthest_from_back_to_front(self, position):
house_position = position - self.back_count - 1
distance = self.front_count
self.front_weight += self.houses[house_position]
self.front_consumption += distance * self.houses[house_position]
def remove_current_position_from_front(self, position):
self.front_consumption -= self.front_weight
self.front_weight -= self.houses[position]
def update_solution(self, position, weight):
(best_position, best_weight) = self.solution
if weight > best_weight:
self.solution = (position, weight)
def initialize_front(self):
weight = 0
consumption = 0
for distance in range(1, self.front_count + 1):
consumption += distance * self.houses[distance]
weight += self.houses[distance]
return (weight, consumption)
def initialize_back(self):
weight = 0
consumption = 0
for distance in range(1, self.back_count + 1):
consumption += distance * self.houses[-distance]
weight += self.houses[-distance]
return (weight, consumption)
结果：
>>> hippo_island([0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2])
(7, 33)
