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

C++ में सभी जोड़ी मोज़े को एक साथ व्यवस्थित करने के लिए आवश्यक न्यूनतम स्वैप्स की संख्या ढूंढने का प्रोग्राम


परिचय

मान लीजिए हमारे पास row नामक संख्याओं की एक सूची है और यह एक पंक्ति में पड़े मोज़े (socks) को दर्शाती है। वे सॉर्टेड नहीं हैं, लेकिन हम उन्हें पुनर्व्यवस्थित करना चाहते हैं ताकि मोज़े की प्रत्येक जोड़ी अगल-बगल हो जैसे (0, 1), (2, 3), (4, 5), और इसी तरह। हमें उन्हें पुनर्व्यवस्थित करने के लिए आवश्यक न्यूनतम स्वैप्स (swaps) की संख्या ढूंढनी है।

तो, यदि इनपुट row = [0, 5, 6, 2, 1, 3, 7, 4] है, तो आउटपुट 2 होगा, क्योंकि पंक्ति के क्रम हैं:

  • [0, 5, 6, 2, 1, 3, 7, 4]
  • [0, 1, 6, 2, 5, 3, 7, 4]
  • [0, 1, 3, 2, 5, 6, 7, 4]
  • [0, 1, 3, 2, 5, 4, 7, 6]

समाधान दृष्टिकोण

यूनियन-फाइंड (डिसजॉइंट सेट यूनियन - DSU) का उपयोग करके। प्रत्येक जोड़ी (0,1), (2,3), ... को एक घटक मानें। वर्तमान व्यवस्था में, यदि एक स्लॉट में जोड़ी u का मोजा और अगले स्लॉट में जोड़ी v का मोजा है, तो u और v को यूनियन करें। उत्तर Σ(size(component) - 1) सभी घटकों के लिए है।

उदाहरण कोड

#include <bits/stdc++.h>
using namespace std;

vector<int> p, sz;

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void join(int u, int v) {
    int pu = find(u), pv = find(v);
    if (pu == pv) return;
    if (sz[pu] >= sz[pv]) {
        p[pv] = pu;
        sz[pu] += sz[pv];
    } else {
        p[pu] = pv;
        sz[pv] += sz[pu];
    }
}

int solve(vector<int>& arr) {
    int n = arr.size() / 2;
    p = vector<int>(n);
    for (int i = 0; i < n; ++i) p[i] = i;
    sz = vector<int>(n, 1);
    for (int i = 0; i < n; ++i) {
        int u = arr[i << 1] / 2;
        int v = arr[i << 1 | 1] / 2;
        join(u, v);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (find(i) == i)
            ans += sz[i] - 1;
    return ans;
}

int main(){
    vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
    cout << solve(v);
    return 0;
}

इनपुट

{0, 5, 6, 2, 1, 3, 7, 4}

आउटपुट

2

नोट

मूल आउटपुट में "23" था जो गलत प्रतीत होता है। सही आउटपुट 2 है जैसा कि चरण-दर-चरण उदाहरण में दिखाया गया है।

निष्कर्ष

DSU-आधारित समाधान O(n α(n)) समय में न्यूनतम स्वैप्स की गणना करता है। प्रत्येक कनेक्टेड कंपोनेंट के आकार k के लिए k-1 स्वैप्स की आवश्यकता होती है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।


  1. - सभी किताबें खरीदने के लिए न्यूनतम लागत खोजें C++ में

    मान लीजिए हमारे पास n तत्वों का एक ऐरे है। ये उनकी रेटिंग हैं। निम्नलिखित शर्त के साथ सभी किताबें खरीदने के लिए न्यूनतम लागत खोजें - प्रत्येक किताब की लागत कम से कम 1 डॉलर होगी एक किताब की लागत आसन्न (बाएं या दाएं) से अधिक होगी यदि रेटिंग आसन्न से अधिक है। तो उदाहरण के लिए, यदि रेटिंग ऐरे [1, 3, 4

  1. - C++ प्रोग्राम ग्राफ को डिस्कनेक्ट करने के लिए काटने के लिए न्यूनतम एजेस की संख्या खोजने के लिए

    इस प्रोग्राम में हमें एक ग्राफ की एज कनेक्टिविटी ढूंढनी है। एक ग्राफ की एज कनेक्टिविटी का अर्थ है यह एक ब्रिज है, इसे हटाने पर ग्राफ डिस्कनेक्ट हो जाएगा। एक डिस्कनेक्टेड अनडायरेक्टेड ग्राफ में ब्रिज को हटाने पर कनेक्टेड कंपोनेंट्स की संख्या बढ़ जाती है। फंक्शन्स और सूडोकोड connections() एक रिकर्सि

  1. - पायथन में सभी 1s को एक साथ समूहित करने के लिए न्यूनतम स्वैप की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी स्ट्रिंग है, हमें सभी 1s को स्ट्रिंग में किसी भी स्थान पर एक साथ समूहित करने के लिए आवश्यक न्यूनतम स्वैप की संख्या ढूंढनी है। उदाहरण के लिए, यदि इनपुट 10101001101 है, तो आउटपुट 3 होगा, क्योंकि संभावित समाधान 00000111111 है। इसे हल करने के लिए हम निम्न चरणों का पालन करें