n فیل در یک ردیف قرار گرفتهاند. هر کدام از فیلها یک شماره بین 1 و n دارند و شماره تمام فیلها متفاوت است.
میدانیم در ابتدا فیل شماره 1≤ai≤n در مکان iام قرار دارد. همچنین وزن فیل شماره i برابر با wi است.
ما میتوانیم در هر مرحله دو فیل i و j را انتخاب کنیم و با پرداخت هزینه wi+wj مکان دو فیل را عوض کنیم. هدف ما رسیدن به حالتی است که فیل شماره bi در مکان i ام قرار داشته باشد. شما باید کمترین هزینه ممکن برای انجام این کار را به دست آورید.
در تنها سطر خروجی پاسخ سؤال را چاپ نمایید.
ورودي نمونه | خروجي نمونه |
---|---|
6 2400 2000 1200 2400 1600 4000 1 4 5 3 6 2 5 3 2 4 6 1 | 11200 |
پاسخ
فرض کنید گراف جهت دار G گرافی با n رأس و n یال جهت دار باشد که به ازای هر i ، یک یال از ai به bi وجود داشته باشد. (به چنین گرافی گراف جایگشت می گویند). چون درجه ورودی و خروجی هر رأس دقیقاً برابر با 1 است، این گراف به تعدادی دور افراز شده است. فرض کنید این دورها c1 تا ck باشند.
به ازای هر دور ci میدانیم که حداقل |ci−1| بار باید فیلهای متناظر رئوس ci را جابهجا کنیم تا تمام فیلها در جای خود قرار بگیرند. اگر بخواهیم با دقیقاً |ci−1| بار جابه جا کردن فیلها این کار را انجام دهیم لزوما تمام جابهجاییها باید بین فیلهای همین دور باشد پس حداقل \sum_{j=1}^{|c_i|}w_{c_{i,j}} + (|c_i|-2) \times \min_{j=1}^{|c_i|}w_{c_{i,j}} هزینه برای این کار لازم و کافی است.
در صورتی که تمام جابهجاییها بین فیلهای دور c_i نباشد ، بیشتر یا مساوی |c_i| جا بهجایی برای این کار لازم است و چون زوجیت تعداد عملیات لازم برای قرار دادن فیلها در جای خود ثابت است ( هر جابهجایی تعداد دور های گراف جایگشت را یکی کم یا زیاد می کند) پس حداقل |c_i+1| جابهجایی برای این کار لازم است. پس در این صورت حداقل \sum_{j=1}^{|c_i|}w_{c_{i,j}} + \min_{j=1}^{|c_i|}w_{c_{i,j}} + (|c_i|+1) \times \min_{j=1}^{n}w_j هزینه برای این کار لازم و کافی است.
پس کافیست به ازای هر دور دو مقدار گفته شده را حساب کنیم و مجموع آنها را به عنوان جواب نهایی چاپ کنیم.