दिया गया कार्य दिए गए बिंदुओं को समाहित करने वाले खंडों की अधिकतम संख्या ढूंढना है।
आकार 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
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है
- main फ़ंक्शन में वेक्टर a1 और a2 और पूर्णांक A और B को कुछ मानों के साथ आरंभ करें।
- चर n1 और n2 बनाएं और उनमें क्रमशः वेक्टर a1 और a2 का आकार संग्रहीत करें।
- Max() फ़ंक्शन में पहले दोनों वेक्टर a1 और a2 को क्रमबद्ध करें।
- वेक्टर a2 और अंतिम उत्तर को क्रमशः ट्रैक करने के लिए j = 0 और ans = 0 आरंभ करें।
- 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 (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 फ़ंक्शन
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