C++ এ গ্যাস স্টেশন থেকে সর্বোচ্চ দূরত্ব কমিয়ে আনুন

ধরুন আমাদের একটি অনুভূমিক সংখ্যা রেখা আছে। সেই নম্বর লাইনে, আমাদের পজিশন স্টেশন[0], স্টেশন[1], ..., স্টেশন [N-1]-এ গ্যাস স্টেশন রয়েছে, যেখানে N =স্টেশন অ্যারের আকার। এখন, আমরা K আরও গ্যাস স্টেশন যোগ করি যাতে D, সংলগ্ন গ্যাস স্টেশনগুলির মধ্যে সর্বাধিক দূরত্ব ন্যূনতম হয়। আমাদের D এর সম্ভাব্য ক্ষুদ্রতম মান খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি স্টেশনের মত হয় =[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K =9, তাহলে আউটপুট হবে 0.5

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন সংজ্ঞায়িত করুন ঠিক আছে(), এটি x, অ্যারে v,

  লাগবে

• ret :=0

• আরম্ভ করার জন্য i :=0, যখন i

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

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• কম :=0

• n :=s

  এর আকার

• উচ্চ :=s[n - 1] - s[0>

• যখন উচ্চ - নিম্ন>=1e-6, করুন −

  • মধ্য :=(নিম্ন + উচ্চ) / 2.0

  • x :=ঠিক আছে(মধ্য, s)

  • যদি x> K, তাহলে −

    • নিম্ন :=মধ্য

  • অন্যথায়

    • উচ্চ :=মধ্য

• উচ্চ রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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