问题1829--bridge1829: bridge
时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
n个人要在晚上过桥,在任何时候最多两人一组过桥,每组要有一只手电筒。在这n个人中只有一只手电筒可以用,因此要安排以某种往返的方式来返还手电筒,使得更多的人可以过桥。
每个人的过桥速度不同,每组的速度由速度较慢的成员所决定的。请您确定一个策略,让n个人用最少的时间过桥。
输入
输入的第一行给出n,接下来的n行给出每个人的过桥时间,不会超过1000人,且没有人过桥超过100秒。
输出
输出的第一行给出所有n个人过桥的总的秒数,接下来的若干行给出实现策略。每行包含一个或两个整数,表示组成一组过桥的一个人或两个人(每个人用其在输入中给出的过桥所用的时间来标识。虽然许多人有相同的过桥时间,但即使有混淆,也对结果没有影响)这里要注意的是过桥也有方向性,因为要返还手电筒让更多的人通过。如果用时最少的策略有多个,则任意一个都可以。
样例输入
4
1
2
5
10
样例输出
17
1 2
1
5 10
2
1 2
提示
本题需要特判,本网站没有那么多时间编写特判,请到以下三个网站在线测试:POJ 2573,ZOJ 1877,UVA 10037
来源/分类
[提交] [状态]