C++ এ ঘূর্ণায়মান দরজা

ধরুন আমাদের কাছে অনুরোধের একটি তালিকা আছে, যেখানে অনুরোধ [i] তে রয়েছে [t, d] ইঙ্গিত করে t সময়ে, একজন ব্যক্তি দরজায় এসেছিলেন এবং হয় ভিতরে যেতে চেয়েছিলেন (ভিতরে 1 ব্যবহার করে ইঙ্গিত করছে) অথবা বাইরে যেতে চান (বাইরে ইঙ্গিত দিচ্ছে) 0) ব্যবহার করে।

সুতরাং যদি শুধুমাত্র একটি দরজা থাকে এবং দরজাটি ব্যবহার করতে এক সময় লাগে, তবে কিছু নিয়ম আছে যা আমাদের অনুসরণ করতে হবে −

• দরজাটি 'ইন' অবস্থান দিয়ে শুরু হয় এবং তারপরে শেষ অংশগ্রহণকারীর দ্বারা ব্যবহৃত অবস্থানে সেট করা হয়৷

• যদি নির্দিষ্ট সময়ে দরজায় শুধুমাত্র একজন অংশগ্রহণকারী থাকে, তাহলে তারা দরজাটি ব্যবহার করতে পারবে।

• যদি দুই বা ততোধিক অংশগ্রহণকারী প্রবেশ করতে চায়, তবে প্রথম দিকে অংশগ্রহণকারী প্রথমে যায় এবং তারপরে পূর্বে ব্যবহৃত দিকটি অগ্রাধিকার পায়।

• যদি কেউ এককালীন ইউনিটের জন্য দরজা ব্যবহার না করে, তবে এটি প্রাথমিক অবস্থায় ফিরে আসে।

সুতরাং, আমাদের বাছাই করা তালিকাটি খুঁজে বের করতে হবে যেখানে প্রতিটি উপাদান রয়েছে [t, d], নির্দেশ করে যে সময় t, একজন ব্যক্তি ভিতরে বা বাইরে গিয়েছিল।

সুতরাং, ইনপুট যদি [[2,0],[3,1],[6,0],[6,1],[3,0]] এর মত হয়, তাহলে আউটপুট হবে [[2,0] ,[3,0],[4,1],[6,1],[7,0]]

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

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

• একটি তালিকা তৈরি করুন

• curr :=1, i :=0, j :=0

• n :=v

  এর আকার

• যখন আমি

  • যদি ret খালি না হয় এবং ret> 1 এর শেষ উপাদানের v[i, 0] - t হয়, তাহলে:

    • curr :=1

  • j :=i + 1

  • আকার 2

    এর একটি অ্যারে অ্যারের সংজ্ঞা দিন

  • (arr[v[i, 1]] 1 দ্বারা বাড়ান)

  • যখন (j

    • (arr[v[j, 1]] 1 দ্বারা বাড়ান)

  • t :=সর্বাধিক (যদি ret খালি হয়, তাহলে 0, অন্যথায় ret-এর শেষ উপাদানের t) এবং v[i, 0]

  • যদি arr[1] হয় অ-শূন্য এবং arr[0] হয় অ-শূন্য, তাহলে −

    • যখন arr[curr] অ-শূন্য হয়, প্রতি ধাপে arr[curr] কমিয়ে দিন −

      • ret

        এর শেষে {t, curr} সন্নিবেশ করান

      • (t 1 দ্বারা বাড়ান)

    • curr :=curr XOR 1

    • যখন arr[curr] অ-শূন্য হয়, প্রতি ধাপে arr[curr] কমিয়ে দিন −

      • ret

        এর শেষে {t, curr} সন্নিবেশ করান

      • (t 1 দ্বারা বাড়ান)

  • অন্যথায়

    • curr :=v[i, 1]

    • যখন arr[curr] অ-শূন্য হয়, প্রতি ধাপে arr[curr] কমিয়ে দিন −

      • ret

        এর শেষে {t, curr} সন্নিবেশ করান

      • (t 1 দ্বারা বাড়ান)

  • curr :=ret এর শেষ উপাদানের দিক

  • i :=j

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

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

উদাহরণ

#include  namespace ব্যবহার করে std;void print_vector(vector> v) { cout <<"["; জন্য (int i =0; i > সমাধান(ভেক্টর<ভেক্টর>&v) { sort(v.begin(), v.end() ); ভেক্টর <ভেক্টর > ret; int curr =1; int i =0; int j =0; int n =v.size(); while(i  1){ curr =1; } j =i + 1; ভেক্টর  arr(2); arr[v[i][1]]++; যখন (j > v ={{2, 0},{3, 1},{6, 0},{6, 1},{3, 0}}; সমাধান ob; print_vector(ob.solve(v));}

ইনপুট

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

আউটপুট