#P2573. Bridge

Bridge

中文题面:

描述

nn 个人希望在夜晚通过一座桥。每次最多允许两人共同过桥,且每组必须携带一只手电筒。

在这 nn 人中仅有一只手电筒可用,因此必须安排某种往返方式以归还手电筒,从而让更多人能够过桥。

每个人的过桥速度不同;一组的速度由其中较慢的成员决定你的任务是设计一种策略,使所有 nn 个人在最短时间内全部过桥。

输入:

输入的第一行为 nn,随后 nn 行依次给出每个人的过桥时间。

总人数不超过 10001000,且每个人的过桥时间均不超过 100100 秒。

输出:

输出的第一行需包含所有人过桥所需的总耗时(秒)。

接下来的每行需给出实现该最短时间的具体策略:

每行包含一个或两个整数,表示下一步过桥的人选(用输入中对应的过桥时间标识)。尽管可能存在多人过桥时间相同的情况,但选择顺序不影响结果。

注意,过桥方向必须交替进行(因需归还手电筒)。若有多重最优策略,输出任意一种即可。

输入数据 1

4
1
2
5
10

输出数据 1

17
1 2
1
5 10
2
1 2

来源

ACM国际大学生程序设计竞赛(ACM-ICPC) 德国乌尔姆大学分站赛