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

C++ में घूमने वाला दरवाजा समस्या


मान लीजिए हमारे पास अनुरोधों की एक सूची है, जहां requests[i] में [t, d] होता है जो दर्शाता है कि समय t पर एक व्यक्ति दरवाजे पर आया और या तो अंदर जाना चाहता था (अंदर को 1 से दर्शाया गया है) या बाहर जाना चाहता था (बाहर को 0 से दर्शाया गया है)।

यदि केवल एक दरवाजा है और इसका उपयोग करने में एक समय इकाई लगती है, तो हमें कुछ नियमों का पालन करना होगा:

  • दरवाजा 'अंदर' स्थिति से शुरू होता है और फिर अंतिम प्रतिभागी द्वारा उपयोग की गई स्थिति पर सेट हो जाता है।
  • यदि दिए गए समय t पर दरवाजे पर केवल एक प्रतिभागी है, तो वे दरवाजे का उपयोग कर सकते हैं।
  • यदि दो या अधिक प्रतिभागी अंदर जाना चाहते हैं, तो सबसे पहले आया प्रतिभागी पहले जाता है और फिर पहले उपयोग की गई दिशा को प्राथमिकता मिलती है।
  • यदि एक समय इकाई तक कोई दरवाजे का उपयोग नहीं करता है, तो यह प्रारंभिक स्थिति पर वापस आ जाता है।

हमें क्रमबद्ध सूची ज्ञात करनी है जहां प्रत्येक तत्व में [t, d] होता है, जो दर्शाता है कि समय t पर एक व्यक्ति या तो अंदर गया या बाहर गया।

उदाहरण के लिए, यदि इनपुट है [[2,0],[3,1],[6,0],[6,1],[3,0]], तो आउटपुट [[2,0],[3,0],[4,1],[6,1],[7,0]] होगा।

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

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • सरणी v को सॉर्ट करें।
  • एक सूची ret बनाएं।
  • curr := 1, i := 0, j := 0
  • n := v का आकार
  • while i < n करते हुए:
    • यदि ret खाली नहीं है और v[i][0] - ret के अंतिम तत्व का t > 1, तो curr := 1
    • j := i + 1
    • आकार 2 की एक सरणी arr परिभाषित करें
    • arr[v[i][1]] बढ़ाएं
    • while (j < n और v[j][0], v[i][0] के समान है):
      • arr[v[j][1]] बढ़ाएं
    • t := अधिकतम (यदि ret खाली है तो 0, अन्यथा ret के अंतिम तत्व का t + 1) और v[i][0]
    • यदि arr[1] और arr[0] दोनों शून्येतर हैं:
      • while arr[curr] शून्येतर है, arr[curr] को प्रत्येक चरण में 1 से घटाएं:
        • {t, curr} को ret के अंत में डालें
        • t बढ़ाएं
      • curr := curr XOR 1
      • while arr[curr] शून्येतर है, arr[curr] को प्रत्येक चरण में 1 से घटाएं:
        • {t, curr} को ret के अंत में डालें
        • t बढ़ाएं
    • अन्यथा:
      • curr := v[i][1]
      • while arr[curr] शून्येतर है, arr[curr] को प्रत्येक चरण में 1 से घटाएं:
        • {t, curr} को ret के अंत में डालें
        • t बढ़ाएं
    • curr := ret के अंतिम तत्व की दिशा
    • i := j
  • ret लौटाएं।

C++ कार्यान्वयन

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

void print_vector(vector<vector<auto>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<int>> solve(vector<vector<int>>& v) {
        sort(v.begin(), v.end());
        vector<vector<int>> ret;
        int curr = 1;
        int i = 0;
        int j = 0;
        int n = v.size();
        while (i < n) {
            if (!ret.empty() && v[i][0] - ret.back()[0] > 1) {
                curr = 1;
            }
            j = i + 1;
            vector<int> arr(2);
            arr[v[i][1]]++;
            while (j < n && v[j][0] == v[i][0]) {
                arr[v[j][1]]++;
                j++;
            }
            int t = max((ret.empty() ? 0 : ret.back()[0] + 1), v[i][0]);
            if (arr[1] && arr[0]) {
                while (arr[curr]--) {
                    ret.push_back({t, curr});
                    t++;
                }
                curr = curr ^ 1;
                while (arr[curr]--) {
                    ret.push_back({t, curr});
                    t++;
                }
            } else {
                curr = v[i][1];
                while (arr[curr]--) {
                    ret.push_back({t, curr});
                    t++;
                }
            }
            curr = ret.back()[1];
            i = j;
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{2, 0}, {3, 1}, {6, 0}, {6, 1}, {3, 0}};
    Solution ob;
    print_vector(ob.solve(v));
    return 0;
}

इनपुट

{{2, 0}, {3, 1}, {6, 0}, {6, 1}, {3, 0}}

आउटपुट

[[2, 0, ],[3, 0, ],[4, 1, ],[6, 1, ],[7, 0, ],]
  1. C++ में जंप गेम V C++ में जंप गेम V

    मान लीजिए हमारे पास arr नामक पूर्णांकों की एक सरणी और एक पूर्णांक d है। एक चरण में हम इंडेक्स i से कूद सकते हैं: i + x जहां: i + x < n और x की सीमा 1 से d है। = 0 और x की सीमा 1 से d है। arr[k] हो। हम सरणी के किसी भी इंडेक्स से कूदना शुरू कर सकते हैं। हमें अधिकतम इंडेक्स की संख्या ज्ञात करनी है ज

  1. - C++ में K डिजिट्स हटाना

    मान लीजिए हमारे पास एक नॉन-नेगेटिव इंटीजर num है जिसे स्ट्रिंग के रूप में दर्शाया गया है, हमें नंबर से k डिजिट्स हटाने हैं ताकि नया नंबर सबसे छोटा संभव हो। उदाहरण के लिए, अगर इनपुट 1432219 है और k = 3, तो रिजल्ट 1219 होगा। इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे: एक स्टैक st डिफाइन करें,

  1. - C++ में चार डिवाइजर्स

    मान लीजिए हमारे पास एक इंटीजर ऐरे nums है, हमें उस ऐरे में उन इंटीजर्स के डिवाइजर्स का योग ढूंढना है जिनके ठीक चार डिवाइजर्स हैं। अगर ऐरे में ऐसा कोई इंटीजर नहीं है, तो 0 लौटाएं। उदाहरण के लिए, अगर इनपुट [21, 4, 7] है, तो आउटपुट 32 होगा, क्योंकि 21 के चार डिवाइजर्स हैं 1, 3, 7, 21, 4 के तीन डिवाइजर