Board logo

標題: 202404潛力3-搭船渡河 [打印本頁]
作者: may    時間: 2024-10-31 16:59     標題: 202404潛力3-搭船渡河

[attach]20122[/attach]
搭船渡河 (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)，兩個正整數之間以一個空白為間隔，表示遊客的體重。
輸出格式
請輸出一個非負整數，表示最少需要幾趟船。
[attach]20121[/attach]
評分說明
此題目測資分成三組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (30 分)：N ≤ 10。
第二組 (40 分)：N ≤ 14。
第三組 (30 分)：無特別限制。
作者: may    時間: 6 天前 16:12

  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <algorithm>
  4. #include <bits/stdc++.h>
  5. using namespace std;

  7. int minBoatTrips(int N, int M, int L, vector<int> weights) {

  9.     sort(weights.begin(), weights.end(), greater<int>());// 依降序排序

  11.     int trips = 0; // 計算行程
  12.     int i = 0, j = N - 1; // 兩個指針指向尚未分配行程的遊客: 最重 (i) and 最輕 (j)

  14.     while (i <= j) {
  15.         int currentWeight = weights[i];
  16.         int passengerCount = 1;//乘客數量

  18.         // 如果符合體重限制，請嘗試與最輕的人 (j) 配對
  19.         while (passengerCount < M  && currentWeight + weights[j] <= L) {  //不能用if
  20.             currentWeight += weights[j];
  21.             passengerCount++;//如果他們可以共用一艘船,就兩人都派,否則就只發送最重的那位
  22.             j--; // 在while迴圈中,更新最輕的遊客,看還能不能再多一個人
  23.         }

  25.         // 增加行程計數並移動最重遊客的指針

  27.         trips++;//發船
  28.         i++;//更新最重的遊客
  29.     }
  30.      return trips;
  31. }

  33. int main() {
  34.     int N, M, L;
  35.     cin >> N >> M >> L;

  37.     vector<int> weights(N);
  38.     for (int i = 0; i < N; i++) {
  39.         cin >> weights[i];
  40.     }

  42.     int result = minBoatTrips(N, M, L, weights);//呼叫minBoatTrips函數回報答案
  43.     cout << result << endl;

  45.     return 0;
  46. }
  47. /*
  48. 4 2 100
  49. 80 35 70 30

  51. 5 3 80
  52. 50 20 30 70 40

  54. */
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2