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