เรือช่วยชีวิตผู้คนใน C++

สมมติว่าเรามีอาร์เรย์ที่เรียกว่าคน ตอนนี้บุคคลที่ i มีน้ำหนักคน[i] และเรือแต่ละลำสามารถบรรทุกน้ำหนักสูงสุดได้ หากเรือแต่ละลำบรรทุกผู้โดยสารได้ไม่เกิน 2 คนพร้อมกัน โดยให้น้ำหนักรวมของคนเหล่านั้นไม่เกินขีดจำกัด เราต้องหาจำนวนเรือขั้นต่ำที่จะบรรทุกได้ทุกคน ดังนั้นหากอินพุตเป็น [3,2,1,2] และจำกัดเป็น 3 เราก็ต้องมีเรือสามลำ [(1,2), (2), (3)].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เรียงลำดับผู้คน

• i :=0, j :=size of people array – 1, ret :=0

• ในขณะที่ฉัน <=j

  • ถ้า people[i] + people[j] <=limit แล้ว i :=i + 1 and j :=j – 1 มิฉะนั้น j :=j – 1

  • ret :=ret + 1

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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;
      int j = people.size() - 1;
      int ret = 0;
      while(i <= j){
         if(people[i] + people[j] <= limit){
               i++, j--;
         }else{
            j--;
         }  
         ret++;
      }
      return ret;
   }
};
main(){
   vector<int> v = {3,2,1,2};
   Solution ob;
   cout << (ob.numRescueBoats(v, 3));
}

อินพุต

[3,2,1,2]
3

ผลลัพธ์

3