讨论/技术交流/求助 | 【腾讯暑实笔试算法题】/
求助 | 【腾讯暑实笔试算法题】

题目描述

高空走钢索,是一项极具危险性的活动,在毫无保护措施的情况下,走上钢索,只有手中的一根长长的平衡棒能够帮助自己掌控平衡。
现在,在钢索一侧,一共有n名练习生,每名练习生都有自己的通过钢索时间。只有在平衡棒的辅助下下才能顺利通过钢索,但是,这些人一共只有一根平衡棒。
由于是练习,离地距离也不高,于是他们决定挑战自我,一次最多两人一起走(必须带有唯的一根平衡棒,前后握住平衡棒,平衡棒和钢索的方向一致)两个人顺利通过钢索的时间为耗时长的那个人的时间。
那么,应该如何安排通过顺序,才能使得所有人都到达钢索另一侧的总耗时最短?请你求出这个最短时长。(假设所有人在过程中零失误,且不会在其它地方耗费时间)
本题为ACM模式,请通过代码实现题目,过程中的输入输出请自行处理,处理方式请参考题目输入输出描述或左侧例题。

输入描述:本题为多组测试数据,第一行輸入一个正整数 T(1 <=T <= 1000),代表测试数据的组数。
对于每组测试数据,第一行输入一个正整数n(1 <= n <= 1000),代表练习生人数。
第二行输入n个正整数t1,t2,...,tn (1<=ti<=100),代表n位练习生各自通过钢索所需要花费的时间。

输入
2
3
3 6 9
4
10 1 5 2

输出
18
17

说明
第一组测试数据:耗时为3和耗时为6的人先过,耗时为3的人独自返回,再跟耗时为9的人公共过,一共所需时间6+3+9=18
第二组测试数据:耗时为1和耗时为2的人先过,耗时为1的人独自返回;
让耗时为5和耗时为10的人过,此时,钢索一侧只有一个耗时为1的人,其余三个人都在另一侧;现在,让耗时为2的人独自返回,带上耗时为1的人再度过钢索。
一共所需时间2+ 1+10+ 2+2=17

共 0 个回复
暂无回复