Computer >> Máy Tính >  >> Lập trình >> C ++

Số lượng mũi tên tối thiểu để bắn bóng bay trong C ++

Giả sử có vài quả bóng bay hình cầu được trải trong không gian hai chiều. Đối với mỗi khinh khí cầu, có tọa độ bắt đầu và kết thúc của đường kính ngang. Bắt đầu luôn nhỏ hơn kết thúc. Sẽ có nhiều nhất 104 quả bóng bay. Một mũi tên có thể được bắn lên chính xác theo chiều dọc từ các điểm khác nhau dọc theo trục x. Một quả bóng bay có vị trí xstart đến xend sẽ nổ tung bởi một mũi tên bắn vào x nếu xstart =x =xend. Không có giới hạn về số lượng mũi tên có thể được bắn. Giả sử rằng một mũi tên sau khi bắn sẽ tiếp tục đi lên vô hạn. Chúng ta phải tìm số lượng mũi tên tối thiểu phải bắn để làm nổ tất cả các quả bóng bay. Vì vậy, nếu đầu vào là [[10,16], [2,8], [1,6], [7,12]], thì đầu ra sẽ là 2. Vì vậy, nếu chúng ta bắn từ x =6, thì nó sẽ nổ [2,8] và [1,6], và một quả bóng bay khác từ x =11 để nổ phần còn lại.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một phương thức có tên là giao nhau () để kiểm tra xem các vị trí có giao nhau hay không

  • Một phương thức khác Thao tác () để thao tác phạm vi sau khi lấy phạm vi của tất cả các bong bóng giao nhau

  • Phương pháp thực tế là lấy các vị trí bong bóng làm vị trí

  • sắp xếp mảng pos dựa trên các vị trí cuối cùng

  • n:=số bong bóng, nếu n là 0 thì trả về 0

  • currEnd:=vị trí cuối của mục nhập đầu tiên của pos sau soring

  • cnt:=1

  • cho tôi trong phạm vi từ 1 đến n - 1

    • nếu currEnd

  • số lần trả lại

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

Ví dụ 

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool intersect(vector <int>& a, vector <int>& b){
      return a[1] >= b[0];
   }
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   void manipulate(vector <int>& a, vector <int>& b){
      a[0] = min(a[0], b[0]);
      a[1] = max(a[1], b[1]);
   }
   int findMinArrowShots(vector<vector<int>>& points) {
      sort(points.begin(), points.end(), cmp);
      int n = points.size();
      if(!n) return 0;
      int currEnd = points[0][1];
      int cnt = 1;
      for(int i = 1; i < n; i++){
         if(currEnd < points[i][0]){
            cnt++;
            currEnd = points[i][1];
         }
      }
      return cnt;
   }
};
main(){
   vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
   Solution ob;
   cout << (ob.findMinArrowShots(v));
}

Đầu vào 

[[10,16],[2,8],[1,6],[7,12]]

Đầu ra 

2