Số lượng phân đoạn tối đa có thể chứa các điểm đã cho trong C ++

Nhiệm vụ được giao là tìm tối đa các đoạn có thể chứa các điểm đã cho.

Cho mảng a1 [] có kích thước n1 và cho trước hai số nguyên A và B. Từ mảng a1 [] đã cho, có thể tạo n1 đoạn thẳng với điểm bắt đầu và điểm kết thúc là a1 [i] - A và a1 [i] + Một cách tổng quát.

Một mảng a2 [] khác được cho với n2 số điểm. Các điểm này phải được chỉ định cho các đoạn thẳng sao cho số lượng đoạn thẳng nhiều hơn số điểm đã được chỉ định là tối đa. Lưu ý rằng một điểm chỉ có thể được chỉ định một lần cho một đoạn thẳng nhất định.

Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ:

Đầu vào

a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2

Đầu ra

Giải thích - Các đoạn thẳng có thể được tạo thành bằng cách sử dụng các điểm a1 [i] - A và a1 [i] + B là (0, 6) và (3, 7).

Điểm đầu tiên trong mảng a2 [], tức là 2 có thể được gán cho đoạn dòng đầu tiên trong khi điểm tiếp theo 8 không thể được gán cho bất kỳ đoạn dòng nào. Do đó, chỉ có thể gán 1 đoạn thẳng cho một điểm và đầu ra trở thành 1.

Đầu vào

a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1

Đầu ra

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Khởi tạo vectơ a1 và a2 và các số nguyên A và B trong hàm chính với các giá trị nhất định.
Tạo biến n1 và n2 và lưu trữ trong chúng, kích thước của vectơ a1 và a2 một cách khách quan.
Trong hàm Max () trước tiên hãy sắp xếp cả hai vectơ a1 và a2.
Khởi tạo j =0 và ans =0 để theo dõi vectơ a2 và câu trả lời cuối cùng một cách khách quan.
Lặp lại từ i =0 đến i
Bên trong vòng lặp For bắt đầu một vòng lặp while khác với điều kiện j
Kiểm tra xem (a1 [i] + B
Khác kiểm tra xem (a2 [j]> =a1 [i] - A &&a2 [j] <=a1 [i] + B). Nếu vậy thì hãy tăng ans vàj và thoát ra khỏi vòng lặp while.
Nếu không có câu nào ở trên là đúng thì chỉ cần tăng j.
trả lại ans

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){
   //sorting a1 and a2
   sort(a1.begin(), a1.end());
   sort(a2.begin(), a2.end());
   int j = 0;
   int ans = 0;
   for (int i = 0; i < n1; i++){
      // searching for point
      while (j < n2){
         /* If ending point of segment is
         smaller than the current point*/
         if (a1[i] + B < a2[j])
            break;
            //
         if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B){
            ans++;
            j++;
            break;
         }
         else
            j++;
      }
   }
   return ans;
}
// main function
int main(){
   int A = 0, B = 1;
   vector<int> a1 = { 1, 2, 3, 4, 6, 7 };
   int n1 = a1.size();
   vector<int> a2 = { 2, 5, 6, 8 };
   int n2 = a2.size();
   cout << Max(a1, a2, n1, n2, A, B);
   return 0;
}