Question

پویا در اتاقش n کشوی روی هم دارد که از پایین تا بالا با اعداد ۱ تا n نام‌گذاری شده‌اند. در ابتدا همه‌ی کشوها بسته‌اند.او در طول روز باید m بار هر بار از یک کشو وسیله‌ای بردارد. برای برداشتن یک وسیله از یک کشو باید آن کشو را باز کند. برای اینکه پویا قادر به باز کردن یا برداشتن یک کشو باشد،باید تمام کشو‌های بالایش بسته شوند. باز کردن یا بستن یک کشو یک ثانیه طول می‌کشد(برداشتن وسیله اصلا طول نمی‌کشد). همچنین چون پویا پسر تنبلی است اگر مجبور نباشد یک کشو را باز یا بسته نمی‌کند. به شما دنباله‌ی شماره‌ کشوهایی که پویا می‌خواهد به ترتیب از آنها وسیله بردارد داده شده است.حساب کنید دست کم چند ثانیه طول می‌کشد تا پویا به ترتیب داده شده از کشو ها بردارد.

ورودی :

خط اول ورودی شامل اعداد m و n است . در m خط بعد شماره کشوهایی که پویا به ترتیب می‌خواهد از آنها وسیله بردارد آمده است.

(n<=1,000,000,000) (m<=100,000)

خروجی:

در یک خط از خروجی کمترین زمان مورد نیاز برای پویا را بنویسید

ورودی نمونه:

خروجی نمونه:

Answer 1

فک کنم سوال چهار رده الف حلی نت هفتمه!
توی پشته(stack) نگه میداریم چه کشو هایی باز هستند!
توی مرحله iام میخوایم کشوی ai رو ببینیم و باید تمام کشوهای باز بیشتر از ai رو ببندیم پس میایم تا وقتی که عدد بالای پشته مون بیشتر از ai , اونو حذف میکنیم, بعد ai رو بهش اضافه میکنیم به ازای هرکدام از این عملیات ها هم یک بار جواب رو زیاد میکنیم.
تو هر مرحله داخل استکمون صعودی میمونه پس اگه توی استک به جایی رسیدیم که دیگه بزرگتر از ai نیست یعنی دیگه هیچ کشوی بالاتری باز نیست!
الگوریتم هم از اردر n است!

آمار پرسش:

پرسش‌های مشابه:

نکاتی در مورد نوشتن پاسخ:

استفاده از ویرایشگر:

علائم ریاضی:

الگوریتمی برای کمینه کردن تعداد دفعات بازشدن کشوها

1 پاسخ

پاسخ شما

پیش‌نمایش: