import heapq import sys from itertools import combinations
defoptimal_dive(times, strategy="auto"): """返回 (最少总用时, 每轮决策列表)。 strategy: "auto" 每轮取 A/B 较小者(最优) "a" / "b" 强制只用某一种(用于对比、复现原写法) """ n = len(times) if n == 0: return0, []
a = sorted(times) total, decisions = 0, [] m = n # 尚未过河的是 a[0..m-1]
while m > 3: a0, a1, x, y = a[0], a[1], a[m - 2], a[m - 1] cost_a = 2 * a0 + x + y cost_b = a0 + 2 * a1 + y use_a = (cost_a <= cost_b) if strategy == "auto"else (strategy == "a") total += cost_a if use_a else cost_b decisions.append({"x": x, "y": y, "A": cost_a, "B": cost_b, "chosen": "A"if use_a else"B"}) m -= 2# 最慢的两人已过河
if m == 1: total += a[0] elif m == 2: total += a[1] elif m == 3: total += a[0] + a[1] + a[2] return total, decisions
defbrute_force(times): """状态压缩 Dijkstra:状态 = (对岸的人集合, 瓶子在哪一岸)。""" n = len(times) if n == 0: return0 full = (1 << n) - 1 dist = {(0, 0): 0} pq = [(0, 0, 0)] # (累计耗时, mask, 瓶子侧 0=起点 1=对岸)
while pq: d, mask, side = heapq.heappop(pq) if d != dist.get((mask, side)): continue if mask == full and side == 1: return d
if side == 0: # 瓶子在起点:送 1 或 2 个人过去 avail = [i for i inrange(n) ifnot (mask >> i) & 1] for k in (1, 2): for group in combinations(avail, k): cost = max(times[i] for i in group) nmask = mask for i in group: nmask |= 1 << i if d + cost < dist.get((nmask, 1), 1 << 60): dist[(nmask, 1)] = d + cost heapq.heappush(pq, (d + cost, nmask, 1)) else: # 瓶子在对岸:只派 1 个人回来(已采用观察 1,不枚举两人同返) for i inrange(n): if (mask >> i) & 1: nmask = mask & ~(1 << i) if d + times[i] < dist.get((nmask, 0), 1 << 60): dist[(nmask, 0)] = d + times[i] heapq.heappush(pq, (d + times[i], nmask, 0))
if __name__ == "__main__": nums = [int(x) for x in sys.stdin.read().split()] n, times = nums[0], nums[1:1 + nums[0]] total, decisions = optimal_dive(times) print(total) for d in decisions: print(f" x={d['x']:>3} y={d['y']:>3} A={d['A']:>4} B={d['B']:>4} -> {d['chosen']}")