Boats to Save People trong C++

Cho mảng people[i] là cân nặng người i, mỗi thuyền chở tối đa 2 người, tổng cân nặng ≤ limit. Tìm số thuyền tối thiểu.

Ví dụ: [3,2,1,2], limit=3 → 3 thuyền [(1,2), (2), (3)].

Giải pháp tham lam hai con trỏ:

• Sort people

• i=0, j=n-1, ret=0

• While i≤j:
  Nếu people[i]+people[j] ≤ limit: i++, j--
  Ngược lại: j--
  ret++

• Trả về ret

Ví dụ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int numRescueBoats(vector<int>& people, int limit) {       sort(people.begin(), people.end());       int i = 0, j = people.size() - 1, ret = 0;       while(i <= j){          if(people[i] + people[j] <= limit){ i++; j--; } else { j--; } ret++; }       return ret;    } }; int main(){ vector<int> v = {3,2,1,2}; Solution ob; cout << ob.numRescueBoats(v, 3); }

Đầu vào

[3,2,1,2] 3

Đầu ra

3