Processing math: 87%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۶۸

Elephants

n‎ فیل در یک ردیف قرار گرفته‌اند. هر کدام از فیل‌ها یک شماره بین ‎1‎ و ‎n‎ دارند و شماره تمام فیل‌ها متفاوت است‎. ‎

می‌دانیم در ابتدا فیل شماره ‎1ain‎ در مکان ‎i‎ام قرار دارد. همچنین وزن فیل شماره ‎i‎ برابر با ‎wi‎ است‎. ‎

ما می‌توانیم در هر مرحله دو فیل ‎i‎ و ‎j‎ را انتخاب کنیم و با پرداخت هزینه ‎wi+wj‎ مکان دو فیل را عوض کنیم. هدف ما رسیدن به حالتی است که فیل شماره ‎bi‎ در مکان ‎i‎ ام قرار داشته باشد. شما باید کم‌ترین هزینه ممکن برای انجام این کار را به دست آورید‎. ‎

ورودی

  • در سطر اول ورودی عدد ‎(1n105)‎ آمده است‎.‎
  • در سطر بعدی ‎n‎ عدد ‎w1‎ تا ‎wn‎ آمده است‎.‎
  • در سطر سوم ‎n‎ عدد ‎a1‎ تا ‎an‎ آمده است‎.‎
  • در سطر چهارم ورودی ‎n‎ عدد ‎b1‎ تا ‎bn‎ آمده است‎.

خروجی

در تنها سطر خروجی پاسخ سؤال را چاپ نمایید‎.

محدودیت‌ها

  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
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‎ می‌دانیم که حداقل ‎|ci1|‎ بار باید فیل‌های متناظر رئوس ‎ci‎ را جابه‌جا کنیم تا تمام فیل‌ها در جای خود قرار بگیرند. اگر بخواهیم با دقیقاً ‎|ci1|‎ بار جابه جا کردن فیل‌ها این کار را انجام دهیم لزوما تمام جا‌به‌جایی‌ها باید بین فیل‌های همین دور باشد پس حد‌اقل ‎\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‎ هزینه برای این کار لازم و کافی است‎.

‎ پس کافیست به ازای هر دور دو مقدار گفته شده را حساب کنیم و مجموع آن‌ها را به عنوان جواب نهایی چاپ کنیم.


ابزار صفحه