দেওয়া টাস্ক হল সর্বাধিক সেগমেন্ট খুঁজে বের করা যাতে প্রদত্ত পয়েন্ট থাকতে পারে।
n1 সাইজ সহ a1[] অ্যারে দেওয়া হয়েছে এবং 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 ভেক্টরের আকার সংরক্ষণ করুন।
-
Max() ফাংশনে প্রথমে a1 এবং a2 উভয় ভেক্টরকে সাজান।
-
ভেক্টর a2 এবং চূড়ান্ত উত্তর যথাক্রমে ট্র্যাক রাখার জন্য j =0 এবং ans =0 শুরু করুন৷
-
i =0 থেকে i
-
ফর লুপের ভিতরে j
-
পরীক্ষা করুন যদি (a1[i] + B
-
অন্যথায় পরীক্ষা করুন যদি (a2[j]>=a1[i] - A &&a2[j] <=a1[i] + B)। যদি তাই হয় তাহলে ans andj বৃদ্ধি করুন এবং while লুপ থেকে বেরিয়ে আসুন।
-
যদি উপরের বিবৃতিগুলির কোনটিই সত্য না হয় তবে শুধুমাত্র 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
