#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
;
}
咋看題意，比較單純的我就以為每次只要用最快的人帶另一個人過去對面，然后回來，這樣就是最短時間。
但作者人很好，因為他在示例數(shù)據(jù)里面已經(jīng)告訴所有像我那樣單純的人，這樣的想法是不對的。
然而實在太單純了，竟然不知道示例數(shù)據(jù)是如何計算出來的，唯有去看discuss了。
看過了以后知道了，如果有兩個人，他們過對面花費的時間都很大，那么把這兩個人捆綁一齊送過去，然后再把對面一個走得很快的人回來，這樣可能更好。
明白了這一點后，我第一個反應(yīng)就是DP，誰知道這題的DP是2^100 （n<=100），我知道自己又錯了。
后來想了一下，只要總是比較一種情況，迭代到最后就可以了。
假設(shè)按耗時從低到高來排序所有人，那么得到序列T0,T1,...,Tn-2,Tn-1
那么到底把兩個走得慢的人捆綁到對面，再送一個“快人”回來的優(yōu)勢有多大呢？算一下就好，取哪兩個“慢人”好呢？當(dāng)然是最慢的。
T1(兩個“快人”過去) + T0（最快的人回來）+ Tn-1（最慢兩人過去） + T1（次快的人回來）
然后就這樣把兩個最慢的人送過去了，而常規(guī)的，用最快的人分別送這兩個慢人過去的計算就不說了。 比較一下就知道哪個方案的優(yōu)勢高。
如果對最慢的兩個人都失去優(yōu)勢，那么對其他剩下的人也是。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
