这是当时严神只得了10分的一道题。
这是一道改变后的过河问题。
严神带领他的队员共 n 人来到一条河边, 发现只有一条船。严神发现,为了保证船只顺利航行,至少需要两人才能顺利划动船,而船本身载重量有限,至多可以载三人。每人过河都需要一个时间 a_i ,而当多人同时划船过河时,所需时间以最慢的人为准。严神想要知道,如果要让 n 人都能顺利过河,至少需要多少时间。
输入包括多组数据。
第一行为数字 T ,代表共有 T 组测试数据。
接下来为 T 组数据。
每组数据占 2 行。
第一行,一个整数 n .
第二行共 n 个整数,代表每个人的过河时间 a_i . 相邻两个整数用一个空格隔开。
对于每组输入, 输出一行一个整数,所有人过河所需最短时间。
3 2 1 2 3 1 2 3 4 1 2 3 4
2 3 9
5 4 1 2 5 10 5 1 2 3 4 5 6 1 2 4 8 16 32 7 1 2 4 7 11 16 22 8 31 41 59 26 53 58 97 93
17 16 56 57 507
对于10%的数据, n ≤ 6 ;
对于20%的数据, n ≤ 20 ;
另有10%的数据, 所有 a_i 相同;
对于40%的数据, n ≤ 1000 ;
对于100% 的数据, 1≤T≤5,2≤N≤10^5,1≤a_i≤10^4 .