【題目鏈接】

ybt 1232：Crossing River
OpenJudge NOI 4.6 702:Crossing River
一本通里的翻譯不夠完整，OpenJudge中的英文原題中有對數據大小的限制：
樣例組數$1\le T\le 20$，人數$n\le 1000$，每個人過河時間$s\le 100$

【題目考點】

1. 貪心

小船過河問題
同樣問題可以參考：CSPJ2021初賽 第15題

【解題思路】

1. 思路

經典小船過河問題
考慮每次將2個人渡到對岸，有兩種方案：
假設參與渡河的4人a、b、c、d的渡河時間分別為：$t_a,t_b,t_c,t_d$且有$t_a\le t_b\le t_c\le t_d$，要將c與d渡到對岸。
方案1：a作為船夫
渡河流程為：a與c到對岸，a回來，a與d到對岸，a回來。
渡河時間為渡河的二人中渡河時間較長的時間，所以該方案的渡河時間為：$2t_a+t_c+t_d$。
顯然在該方案下，$t_a$越小渡河時間越短。所以a應該為渡河時間最短的人。
方案2：a與b作為船夫
渡河流程為：a與b到對岸，a回來，c與d到對岸，b回來。
該方案的渡河時間為：$2t_b+t_a+t_d$
顯然在該方案下，$t_a$與$t_b$應該盡可能小，而$t_c$應該盡量接近$t_d$。

其他將兩個人渡到對岸的方案，都不如上述兩種方案。這里不再做詳細論證。
而上述兩種方案的優劣是不固定的，所以需要每次判斷哪種方案的渡河時間更短。

2. 具體做法

將渡河時間升序排序，選擇渡河時間最短的兩個人作為船夫a與b，每次選擇渡河時間最長的兩個人作為c與d進行渡河。比較兩種渡河方案，看哪種方案渡河時間更短，選擇渡河時間更短的渡河方案。
重復上述過程，每次渡過去兩個人，直到剩余人數小于4。
如果剩下3人，按渡河時間從小到大分別為a，b，c，那么最佳的渡河方案為：a與c到對岸，a回來，a與b到對岸，渡河時間為：$t_a+t_b+t_c$。
如果剩下2人，則a，b兩人可以直接渡到對岸，渡河時間為$t_b$。
如果剩下1人（【注意】如果一共只有1個人，就會出現這種情況。），那么渡河時間為$t_a$。
統計渡河總時間，輸出。

【題解代碼】

解法1：貪心

#include <bits/stdc++.h> using namespace std; #define N 1005 int main() {int n, m, t[N];cin >> m;while(m--){int sum = 0; int i;cin >> n;for(i = 1; i <= n; ++i)cin >> t[i];sort(t+1,t+1+n);for(i = n; i >= 4; i-=2)sum += min(2*t[1]+t[i]+t[i-1], t[1]+2*t[2]+t[i]);if(i == 3)sum += t[1]+t[2]+t[3];else if(i == 2)sum += t[2];else//i == 1 如果只有一個人，那么就會出現這種情況 sum += t[1];cout << sum << endl;}return 0; } 新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1232：Crossing River | OpenJudge NOI 4.6 702:Crossing River的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。