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

C++ में गैस स्टेशन तक अधिकतम दूरी को न्यूनतम करें

मान लीजिए हमारे पास एक क्षैतिज संख्या रेखा है। उस संख्या रेखा पर, हमारे पास गैस स्टेशन positions stations[0], stations[1], ..., stations[N-1] पर हैं, जहां N = stations ऐरे का आकार है। अब, हम K और गैस स्टेशन जोड़ते हैं ताकि D, आसन्न गैस स्टेशनों के बीच अधिकतम दूरी, न्यूनतम हो। हमें D का न्यूनतम संभव मान ज्ञात करना है।

तो, यदि इनपुट stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9 है, तो आउटपुट 0.5 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

  • एक फ़ंक्शन ok() परिभाषित करें, जो x, ऐरे v लेगा,

  • ret := 0

  • i := 0 से शुरू करें, जब i < v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:

    • ret := ret + (v[i + 1] - v[i]) / x की सीलिंग

  • ret लौटाएं

  • मुख्य मेथड से निम्नलिखित करें:

  • लो := 0

  • n := s का आकार

  • हाई := s[n - 1] - s[0]

  • जब हाई - लो >= 1e-6, करें:

    • मिड := (लो + हाई) / 2.0

    • x := ok(मिड, s)

    • यदि x > K, तो:

      • लो := मिड

    • अन्यथा:

      • हाई := मिड

  • हाई लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

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

class Solution {
public:
    int ok(double x, vector& v) {
        int ret = 0;
        for (int i = 0; i < v.size() - 1; i++) {
            ret += ceil((v[i + 1] - v[i]) / x) - 1;
        }
        return ret;
    }

    double minmaxGasDist(vector& s, int K) {
        double low = 0;
        int n = s.size();
        double high = s[n - 1] - s[0];
        while (high - low >= 1e-6) {
            double mid = (low + high) / 2.0;
            int x = ok(mid, s);
            if (x > K) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return high;
    }
};

int main() {
    Solution ob;
    vector v = {1,2,3,4,5,6,7,8,9,10};
    cout << (ob.minmaxGasDist(v, 9));
}

इनपुट

{1,2,3,4,5,6,7,8,9,10}, 9

आउटपुट

0.5
  1. - C++ में वन एडिट डिस्टेंस

    मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं; हमें जांचना है कि क्या वे दोनों वन एडिट डिस्टेंस पर हैं। वन एडिट डिस्टेंस के तीन प्रकार हैं:s में एक कैरेक्टर डालकर t प्राप्त करनाs से एक कैरेक्टर हटाकर t प्राप्त करनाs के एक कैरेक्टर को बदलकर t प्राप्त करनाइसलिए, यदि इनपुट है s = ab, t = acb, तो आउटपुट

  1. C++ में किसी भी शहर और स्टेशन के बीच अधिकतम दूरी खोजें C++ में किसी भी शहर और स्टेशन के बीच अधिकतम दूरी खोजें

    अवधारणा0 से N-1 तक संख्या वाले शहरों की दी गई संख्या N और जिन शहरों में स्टेशन स्थित हैं, के संबंध में, हमारा कार्य किसी भी शहर और उसके निकटतम स्टेशन के बीच अधिकतम दूरी निर्धारित करना है। यह ध्यान दिया जाना चाहिए कि स्टेशनों वाले शहर किसी भी क्रम में दिए जा सकते हैं।इनपुटnumOfCities = 6, stations =

  1. C++ में एक रेखा पर अधिकतम बिंदु C++ में एक रेखा पर अधिकतम बिंदु

    मान लीजिए हमारे पास एक 2D तल है। हमें उन अधिकतम बिंदुओं की संख्या ढूंढनी है जो एक ही सीधी रेखा पर स्थित हैं। तो यदि बिंदु इस तरह हैं -तो 4 बिंदु हैंइसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -n := बिंदुओं की संख्या, यदि n < 3, तो n लौटाएंans := 2i को 1 से n - 1 तक की रेंज मेंcount := 0इं