C++ এ পরপর II পর্যন্ত পাথর সরানো

ধরুন আমরা একটি অসীম সংখ্যা রেখা বিবেচনা করছি, এখানে i−th পাথরের অবস্থান অ্যারে পাথর দ্বারা দেওয়া হয়েছে এবং পাথর [i] পাথরের অবস্থান নির্দেশ করছে। একটি পাথর একটি শেষ বিন্দু পাথর যদি এটি সবচেয়ে ছোট বা বৃহত্তম অবস্থান থাকে। এখন প্রতিটি মোড়ে, আমরা একটি শেষবিন্দু পাথর তুলে নিই এবং এটিকে একটি অব্যক্ত অবস্থানে নিয়ে যাই যাতে এটি আর শেষবিন্দু পাথর না থাকে।

যদি পাথরগুলি বলা হয়, পাথর =[1,2,5], আমরা 5 অবস্থানে শেষবিন্দুর পাথরটিকে সরাতে পারি না, কারণ এটিকে যেকোনো অবস্থানে (যেমন 0, বা 3) সরানো এখনও সেই পাথরটিকে একটি শেষবিন্দু পাথর হিসাবে রাখবে। .

এই খেলা বন্ধ হয়ে যাবে যখন আমরা আর কোনো পদক্ষেপ নিতে পারব না। তাই পাথরগুলো পরপর অবস্থানে রয়েছে।

এখানে আমাদের খুঁজে বের করতে হবে কখন খেলাটি শেষ হবে, তাই সর্বনিম্ন এবং সর্বাধিক সংখ্যক পদক্ষেপগুলি কী হবে যা আমরা তৈরি করতে পারতাম? একটি জোড়া হিসাবে উত্তর খুঁজুন [min_moves, max_moves]

উদাহরণস্বরূপ, যদি ইনপুটটি [7,3,9] এর মত হয়, তাহলে ফলাফল হবে [1,3]

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

• আকার 2

  এর একটি অ্যারে উত্তর সংজ্ঞায়িত করুন

• ans[0] :=inf, ans[1] :=−inf এবং n :=a এর আকার

• অ্যারে সাজান a

• x :=1

• যখন x

  • x 1 দ্বারা বাড়ান

• যদি x n এর মত হয়, তাহলে,

  • একটি জোড়া {0,0}

    ফেরত দিন

• minVal :=0, j :=1

• শুরু করার জন্য i :=0, যখন i

  • curr :=a[i], lastPossible =a[i]

  • যদি lastPossible> a[n - 1], তাহলে, লুপ থেকে বেরিয়ে আসুন

  • spaceInBetween :=মিথ্যা

  • যদি j <=i, তারপর,

    • j :=i + 1

  • যখন j

    • যদি a[j] - a[j - 1])> 1, তারপর,

      • spaceInBetween :=সত্য

    • যদি a[j] - a[j - 1])> 1, তারপর,

    • 1 দ্বারা j বাড়ান

  • idx :=j - 1

  • যদি n - (idx - i + 1)> 1, তারপর,

    • spaceInBetween :=সত্য

• বলবাম :=i, বলরাইট :=n - (idx + 1)

• minVal :=ballLeft + ballRight + (0 যখন spaceInBetween সত্য হয়, অন্যথায় 1)

• ans[0] :=ন্যূনতম ন্যূনতম উত্তর উত্তর [0]

• ans[1] :=a[n - 2] - a[0] এবং a[n - 1] - a[1]) - (n - 2),

• উত্তর ফেরত দিন

• মূল পদ্ধতি থেকে কল সল্ভ(স্টোন)

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> solve(vector<int> a) {
      vector <int> ans(2);
      ans[0] = INT_MAX;
      ans[1] = INT_MIN;
      int n = a.size();
      sort(a.begin(), a.end());
      int x = 1;
      while(x < n && a[x] - a[x - 1] == 1)
         x ++;
      if(x == n){
         return {0,0};
      }
      int minVal = 0;
      int j = 1;
      for(int i = 0; i < a.size(); i++){
         int curr = a[i];
         int lastPossible = a[i] + n - 1;
         if(lastPossible > a[n - 1])
            break;
         bool spaceInBetween = false;
         if(j <= i)
            j = i + 1;
            while(j < n && a[j] <= lastPossible){
               if((a[j] - a[j - 1]) > 1) {
                  spaceInBetween = true;
               }
               j++;
            }
           int idx = j - 1;
           if(n - (idx - i + 1) > 1)
              spaceInBetween = true;
           int ballLeft = i;
           int ballRight = n - (idx + 1);
           minVal = ballLeft + ballRight + (spaceInBetween? 0 : 1);
           ans[0] = min(minVal, ans[0]);
        }
       ans[1] = max(a[n - 2] - a[0], a[n - 1] - a[1]) - (n -2);
       return ans;
   }
   vector<int> numMovesStonesII(vector<int>& stones) {
      return solve(stones);
   }
};
main(){
   Solution ob;
   vector<int> v1 = {7,3,9};
   print_vector(ob.numMovesStonesII(v1));
}

ইনপুট

[7,3,9]

আউটপুট

[1, 3, ]