دوشیدن شیر گاوها

Question

سیامک و پدربزرگش در مزرعه اند. آن ها امروز باید گاوها را بدوشند. n گاو در یک ردیف نشسته اند و از چپ به راست از 1 تا n شماره گذاری شده اند. هر گاو یا به سمت راست است یا به سمت چپ.وقتی او یک گاو را می دوشد تمام گاوهایی که به آن سمت قرار دارند می ترسند و یک واحد شیر خود را از دست می دهند. یک گاو به سمت چپ می تواند تمام گاوهایی که در اندیس های کمتر از اندیس او قرار دارند را ببیند و هر گاو به سمت راست می تواند تمام گاوهایی که اندیس آن ها بیشتر از اندیس اوست را ببیند. یک گاو می تواند بیش از یک بار بترسد. یک گاوی که دوشیده شده دیگر نمی ترسد و به همین خاطر شیری از دست نمی دهد.
سیامک می تواند ترتیب دوشیدن گاوها را تعیین کند اما هر گاو را می تواند فقط یک بار بدوشد. او می خواهد کم ترین مقدار شیر ممکن را از دست بدهد. کمترین مقدار شیر از دست رفته را چاپ کنید.

 

ورودی

اولین خط ورودی شامل عدد صحیح n (1 ≤ n ≤ 200000) می باشد. دومین خط ورودی شامل n عدد صحیح a1, a2, ..., an می باشد که ai در صورتی که گاو به سمت چپ باشد 0 است و در غیر این صورت 1 می باشد.

خروجی

یک عدد که کمترین مقدار شیر از دست رفته است را چاپ کنید.

 

Comments

جدی هرکی بتونه جواب بده
من خیلی فکر کردم نشد که نشد

Answer 1

این راهیه که به ذهن من رسید

تعداد خونه های 0 رو میشماری اسم  X

تعداد 1 ها رو 0میزاری اسم Y

یک لیست دیگه میسازی باسایز n  --> اسم L برای ذخیره ضرر حذف هر خونه

L رو پیمایش می کنی به هر خونه که رسیدی تعداد X ها + Y ها رو میزاری داخل اون خونه حالا اگر توی لیستی که از ورودی گرفتی اندیس معادل اون خونه 1 بود X رو یکی اضافه می کنی اگر 0 بود Y ها رو یکی کم می کنی !

مراحل بالا رو اگر درست بنویسی در کل نیاز به یک بار پیمایش لیست داری . (O(n

بعد حالا داخل  L که مقدار دادی min رو پیدا می کنی حذف می کنی بعد اگر اندیس معادل از لیست ورودی 0 بود خونه های سمت چپ L اونایی که 1 هستو  رو مقدارشون رو همشونو -1 می کنی اگر 1 بود خونه های سمت راست L همشون  رو یک واحد کم می کنی  و مقدار min رو با متغیر خروجی += می کنی این مرحله رو تا وقتی که  L خالی نشده تکرار می کنی

Comments

همچین فکرایی به سر منم زد ولی نمیشه پیاده سازیش کنی
پیاده سازیش سخته

---

چرا سخته یک آرایه میسازی کارایی که گفتمو داخلش انجام میدی
بعد میتونی آرایه رو به heap تبدیل کنی مرحله پیدا کردن min و حذف کردن رو با heap انجام بدی