#P2573. Bridge
Bridge
中文题面:
描述
有 个人希望在夜晚通过一座桥。每次最多允许两人共同过桥,且每组必须携带一只手电筒。
在这 人中仅有一只手电筒可用,因此必须安排某种往返方式以归还手电筒,从而让更多人能够过桥。
每个人的过桥速度不同;一组的速度由其中较慢的成员决定你的任务是设计一种策略,使所有 个人在最短时间内全部过桥。
输入:
输入的第一行为 ,随后 行依次给出每个人的过桥时间。
总人数不超过 ,且每个人的过桥时间均不超过 秒。
输出:
输出的第一行需包含所有人过桥所需的总耗时(秒)。
接下来的每行需给出实现该最短时间的具体策略:
每行包含一个或两个整数,表示下一步过桥的人选(用输入中对应的过桥时间标识)。尽管可能存在多人过桥时间相同的情况,但选择顺序不影响结果。
注意,过桥方向必须交替进行(因需归还手电筒)。若有多重最优策略,输出任意一种即可。
输入数据 1
4
1
2
5
10
输出数据 1
17
1 2
1
5 10
2
1 2
来源
ACM国际大学生程序设计竞赛(ACM-ICPC) 德国乌尔姆大学分站赛