Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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 लाइन खंड को एक बिंदु असाइन किया जा सकता है और आउटपुट 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
  1. - ग्रिड में अधिकतम रोशन की जा सकने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल अपने दाएँ, बाएँ, ऊपर और नीचे की सेल्स को रोशन करता है और प्रकाश सेल्स के माध्यम से चमक सकता है जब तक कि कोई बाधा सेल प्रकाश को न रोक दे। बाधा सेल को रोशन नहीं किया जा सकता और यह बल्ब के प्रकाश क

  1. ग्राफ से घटाए जा सकने वाले अधिकतम स्कोर की मात्रा ज्ञात करने का C++ प्रोग्राम ग्राफ से घटाए जा सकने वाले अधिकतम स्कोर की मात्रा ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक भारित, निदेश रहित ग्राफ दिया गया है। ग्राफ का स्कोर ग्राफ में सभी एज भारों का योग है। एज भार ऋणात्मक हो सकते हैं, और यदि उन्हें हटा दिया जाए तो ग्राफ का स्कोर बढ़ जाता है। हमें ग्राफ को संबद्ध रखते हुए एज हटाकर ग्राफ के स्कोर को न्यूनतम करना है। हमें घटाए जा सकन

  1. C++ में N सेगमेंट का उपयोग करके सेवन सेगमेंट डिस्प्ले पर प्रदर्शित अधिकतम संख्या C++ में N सेगमेंट का उपयोग करके सेवन सेगमेंट डिस्प्ले पर प्रदर्शित अधिकतम संख्या

    दिया गया कार्य N सेगमेंट का उपयोग करके किसी भी संख्या के सेवन सेगमेंट डिस्प्ले पर प्रदर्शित की जा सकने वाली अधिकतम संख्या ढूंढना है।उदाहरण से समझते हैंइनपुट - N=5आउटपुट - 71व्याख्या - सबसे बड़ी संख्या सेवन सेगमेंट डिस्प्ले पर इस प्रकार प्रदर्शित होगी।इनपुट - N=6आउटपुट - 111प्रयुक्त दृष्टिकोणनिम्नलिख