问题1829--bridge

1829: 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

来源/分类

ad hoc 

[提交] [状态]