202404潛力3-搭船渡河

may

搭船渡河 (Boat)
問題敘述
有N位體重分別為W1, W2, …, WN單位的遊客準備搭船渡河，船隻的最大載客數量為 M人，載重量為 L。請幫遊客們計算出最少需要幾趟船才能讓他們全部都渡河。假設我們不考慮船夫的重量、而且只有這N位遊客需要渡河。
例如：有N = 4位遊客體重分別為W1 = 80, W2 = 70, W3 = 75, W4 = 30單位，船隻的最大載客數量為M  = 2人，載重量為L = 100單位，則最少需要3趟船，編號1和3各需要一艘船、編號2和4可共乘一艘船。
輸入格式
第一列有三個正整數N, M, L ( M ≤ N ≤ 17, L ≤ 106 )，表示有N位遊客、船隻的最大載客數量為M人，載重量為L。第二列有N個正整數W1, W2, …, WN (W1, W2, …, WN ≤ L)，兩個正整數之間以一個空白為間隔，表示遊客的體重。
輸出格式
請輸出一個非負整數，表示最少需要幾趟船。

評分說明
此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (30 分)：N ≤ 10。
第二組 (40 分)：N ≤ 14。
第三組 (30 分)：無特別限制。

may

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <algorithm>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. int minBoatTrips(int N, int M, int L, vector<int> weights) {
   
8. 
   
9.     sort(weights.begin(), weights.end(), greater<int>());// 依降序排序
   
10. 
    
11.     int trips = 0; // 計算行程
    
12.     int i = 0, j = N - 1; // 兩個指針指向尚未分配行程的遊客: 最重 (i) and 最輕 (j)
    
13. 
    
14.     while (i <= j) {
    
15.         int currentWeight = weights[i];
    
16.         int passengerCount = 1;//乘客數量
    
17. 
    
18.         // 如果符合體重限制，請嘗試與最輕的人 (j) 配對
    
19.         while (passengerCount < M  && currentWeight + weights[j] <= L) {  //不能用if
    
20.             currentWeight += weights[j];
    
21.             passengerCount++;//如果他們可以共用一艘船,就兩人都派,否則就只發送最重的那位
    
22.             j--; // 在while迴圈中,更新最輕的遊客,看還能不能再多一個人
    
23.         }
    
24. 
    
25.         // 增加行程計數並移動最重遊客的指針
    
26. 
    
27.         trips++;//發船
    
28.         i++;//更新最重的遊客
    
29.     }
    
30.      return trips;
    
31. }
    
32. 
    
33. int main() {
    
34.     int N, M, L;
    
35.     cin >> N >> M >> L;
    
36. 
    
37.     vector<int> weights(N);
    
38.     for (int i = 0; i < N; i++) {
    
39.         cin >> weights[i];
    
40.     }
    
41. 
    
42.     int result = minBoatTrips(N, M, L, weights);//呼叫minBoatTrips函數回報答案
    
43.     cout << result << endl;
    
44. 
    
45.     return 0;
    
46. }
    
47. /*
    
48. 4 2 100
    
49. 80 35 70 30
    
50. 
    
51. 5 3 80
    
52. 50 20 30 70 40
    
53. 
    
54. */

複製代碼