C ++中可以包含给定点的最大段数

给定任务是找到可以包含给定点的最大段数。

给定一个大小为n1的数组a1 []，并给出了两个整数A和B。从给定的数组a1 []可以形成n1线段，起点和终点分别为a1 [i] – A和a1 [i] +B。

另一个数组a2 []的点数为n2。这些点必须分配给线段，以使分配给一个点的线段数量最大。请注意，单个点只能分配给给定的线段一次。

现在让我们使用一个示例来了解我们必须做什么：

输入项

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

在以下程序中使用的方法如下

• 使用特定值初始化向量a1和a2以及主函数中的整数A和B。

• 创建变量n1和n2并分别存储向量a1和a2的大小。

• 在Max()函数中，首先对向量a1和a2进行排序。

• 初始化j = 0和ans = 0分别跟踪向量a2和最终答案。

• 从i = 0循环直到i <n1。

• 在For循环内，启动条件j <n2的另一个while循环。

• 检查是否（a1 [i] + B <a2 [j]）。如果是这样，则打破while循环。

• 否则检查（a2 [j]> = a1 [i]-A && a2 [j] <= a1 [i] + B））。如果是这样，则增加ans和j并退出while循环。

• 如果以上陈述均不成立，则只需递增j。

• 返回ans

示例

#include <bits/stdc++.h>
using namespace std;
int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){
   //排序a1和a2-
   sort(a1.begin(), a1.end());
   sort(a2.begin(), a2.end());
   int j = 0;
   int ans = 0;
   for (int i = 0; i < n1; i++){
      //寻找点
      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;
}
//主要功能
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