資料結構
網路
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 次檢視
廣告