C++で指定されたポイントを含むことができるセグメントの最大数

与えられたタスクは、与えられたポイントを含むことができるセグメントの最大数を見つけることです。

サイズn1の配列a1[]が与えられ、2つの整数AとBが与えられます。指定された配列a1[]から、開始点と終了点をそれぞれa1 [i] –Aおよびa1[i]+としてn1線分を形成できます。

別の配列a2[]は、n2個の点で与えられます。これらのポイントは、ポイントが割り当てられているよりも多くのラインセグメントが最大になるように、ラインセグメントに割り当てる必要があります。1つのポイントは、特定のラインセグメントに1回だけ割り当てることができることに注意してください。

例を使用して、私たちがしなければならないことを理解しましょう：

入力

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

出力

1

説明 −点a1 [i] –Aおよびa1[i] + Bを使用して形成できる線分は、（0、6）および（3、7）です。

配列a2[]の最初のポイント、つまり2は最初の線分に割り当てることができますが、次のポイント8はどの線分にも割り当てることができません。したがって、ポイントを割り当てることができる線分は1つだけで、出力は1になります。

入力

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

出力

4

以下のプログラムで使用されるアプローチは次のとおりです

• main関数のベクトルa1とa2、および整数AとBを特定の値で初期化します。

• 変数n1とn2を作成し、それぞれベクトルa1とa2のサイズを格納します。

• Max（）関数では、最初にベクトルa1とa2の両方を並べ替えます。

• ベクトルa2と最終的な答えをそれぞれ追跡するために、j=0とans=0を初期化します。

• i=0からi

• Forループ内で、条件j

• （a1 [i] + B

• それ以外の場合は、（a2 [j]> =a1 [i]-A &&a2 [j] <=a1 [i] + B）かどうかを確認します。その場合は、ans andjをインクリメントし、whileループから抜け出します。

• 上記のいずれにも当てはまらない場合は、jをインクリメントしてください。

• 回答を返す

例

#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;
}

出力

4