#include
<
iostream
>
#include
<
vector
>
#include
<
algorithm
>
using
namespace
std;
int
main() {
vector
<
int
>
times;
int
n, min
=
0
, t, t1, t2;
cin
>>
n;
for
(
int
i
=
0
;i
<
n;i
++
) {
cin
>>
t;
times.push_back(t);
}
sort(times.begin(), times.end());
for
(
int
i
=
times.size()
-
1
; i
>=
3
; i
-=
2
) {
t1
=
times[
1
]
+
times[
0
]
+
times[i]
+
times[
1
];
t2
=
times[i]
+
times[
0
]
+
times[i
-
1
]
+
times[
0
];
if
( t1
<=
t2 ) {
times.pop_back();
times.pop_back();
min
+=
t1;
}
else
{
break
;
}
}
for
(
int
i
=
times.size()
-
1
; i
>
1
; i
--
) {
min
+=
times[i]
+
times[
0
];
times.pop_back();
}
if
(times.size()
==
2
)
min
+=
times[
1
];
else
min
+=
times[
0
];
cout
<<
min
<<
endl;
return
0
;
}
咋看题意，比较单纯的我就以为每次只要用最快的人带另一个人过去对面，然后回来，这样就是最短时间。
但作者人很好，因为他在示例数据里面已经告诉所有像我那样单纯的人，这样的想法是不对的。
然而实在太单纯了，竟然不知道示例数据是如何计算出来的，唯有去看discuss了。
看过了以后知道了，如果有两个人，他们过对面花费的时间都很大，那么把这两个人捆绑一齐送过去，然后再把对面一个走得很快的人回来，这样可能更好。
明白了这一点后，我第一个反应就是DP，谁知道这题的DP是2^100 （n<=100），我知道自己又错了。
后来想了一下，只要总是比较一种情况，迭代到最后就可以了。
假设按耗时从低到高来排序所有人，那么得到序列T0,T1,...,Tn-2,Tn-1
那么到底把两个走得慢的人捆绑到对面，再送一个“快人”回来的优势有多大呢？算一下就好，取哪两个“慢人”好呢？当然是最慢的。
T1(两个“快人”过去) + T0（最快的人回来）+ Tn-1（最慢两人过去） + T1（次快的人回来）
然后就这样把两个最慢的人送过去了，而常规的，用最快的人分别送这两个慢人过去的计算就不说了。 比较一下就知道哪个方案的优势高。
如果对最慢的两个人都失去优势，那么对其他剩下的人也是。
