数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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。
输入
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){
//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
更新于: 2020年8月3日
201 次查看
广告