给定任务是找到可以包含给定点的最大段数。
给定一个大小为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