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