সি++-এ গ্যাস স্টেশনে সর্বোচ্চ দূরত্ব মিনিমাইজ করা

ধরা যাক একটি হরিজন্টাল নাম্বার লাইন আছে। সেটির ওপর গ্যাস স্টেশনগুলো অবস্থিত 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, array v নেবে,

• ret := 0

• i := 0 থেকে শুরু করুন, যখন i < v-এর আকার, (i ১ করে বাড়ান), করুন -

  • ret := ret + (v[i + 1] - v[i]) / x-এর সিলিং

• ret রিটার্ন করুন

• মূল মেথড থেকে নিচের কাজগুলো করুন -

• low := 0

• n := s-এর আকার

• high := s[n - 1] - s[0]

• যখন high - low >= 1e-6, করুন -

  • mid := (low + high) / 2.0

  • x := ok(mid, s)

  • যদি x > K, তবে -

    • low := mid

  • অন্যথায়

    • high := mid

• high রিটার্ন করুন

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -

উদাহরণ

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int ok(double x, vector <int>& 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<int>& 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;    } }; main(){    Solution ob;    vector<int> 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