दिए गए बिंदुओं को समाहित करने वाले अधिकतम खंडों को खोजने का कार्य दिया गया है।
एक सरणी को देखते हुए a1[] आकार n1 के साथ और दो पूर्णांक A और B दिए गए हैं। दिए गए एरे से a1[],n1 लाइन सेगमेंट को शुरुआती और अंतिम बिंदुओं के साथ a1[i] – A और a1[i] + क्रमशः बनाया जा सकता है।
एक अन्य सरणी 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 के आकार को स्टोर करें।
-
मैक्स () फ़ंक्शन में पहले दोनों वैक्टर a1 और a2 को सॉर्ट करें।
-
क्रमशः वेक्टर a2 और अंतिम उत्तर का ट्रैक रखने के लिए j =0 और ans =0 को प्रारंभ करें।
-
लूप i =0 से i
-
फॉर लूप के अंदर एक और जबकि लूप कंडीशन j
-
जांचें कि क्या (ए 1 [i] + बी <ए 2 [जे])। अगर ऐसा है तो थोड़ी देर के लूप से बाहर निकलें।
-
और जांचें कि क्या (a2[j]>=a1[i] - A &&a2[j] <=a1[i] + B)। यदि ऐसा है तो उत्तर और j को बढ़ाएँ और जबकि लूप से बाहर निकलें।
-
यदि उपरोक्त में से कोई भी कथन सत्य नहीं है, तो केवल j बढ़ाएँ।
- वापसी उत्तर
उदाहरण
#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
