المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۴:سوال ۷

Traffic

کارخانه‌ی پفک‌سازی برای رفاه کارکنانش، هزینه‌‌ی رفت و آمد آن‌ها را تقبل کرده است. کارکنان برای رفت و آمد می‌توانند از تاکسی‌های شخصی و یا اتوبوس‌های مخصوص کارخانه استفاده کنند. کارخانه و خانه‌ی کارمندان همه در یک خیابان بلند قرار دارند و کارخانه در نقطه‌ی صفر خیابان قرار گرفته است. مختصات خانه‌ها می‌تواند منفی باشد. هزینه‌ی استفاده از تاکسی به ازای هر متر برابر ۱ تومان است، در صورتی که استفاده از اتوبوس‌های کارخانه، رایگان هستند. تنها هزینه‌ای که حمل و نقل اتوبوس‌ها بر کارخانه تحمیل می‌کند، نگهداری از ایستگاه‌های اتوبوس است (از هزینه‌ی ساخت ایستگاه صرف نظر می‌شود). هزینه‌ی نگهداری از ایستگاه اتوبوس را $c$ تومان در نظر بگیرید. هم‌چنین می‌دانیم بدون استفاده از تاکسی‌ها و تنها با استفاده از اتوبوس‌ها، می‌توان از هر ایستگاه اتوبوسی به هر ایستگاه دیگری رسید.

حال مسئولین کارخانه قصد دارند تعدادی ایستگاه اتوبوس درست کنند به طوری که هزینه‌ی روزانه‌ای که باید بابت حمل و نقل پرداخت کنند، کمینه شود. فرض می‌شود که تمامی کارکنان توسط ارزان‌ترین مسیر به خانه‌شان می‌روند. بنابراین اگر تعداد ایستگاه‌های ساخته شده را $k$ بگیریم و مجموع مسافتی که کارمندان از تاکسی استفاده خواهند کرد برابر با $t$ باشد (با این فرض که همه‌ی کارمندان در ابتدا در خانه‌ی صفر هستند و کارمند شماره‌ی $i$‌قصد دارد به مختصات $x_i$ برود)، هزینه‌ی کارخانه مساوی $kc+t$ می‌شود.

برنامه‌ای بنویسید که کم‌ترین هزینه برای رفت و ‌آمد کارکنان را محاسبه کند.

ورودی

در سطر اول ورودی دو عدد طبیعی $n$، تعداد کارکنان و $c$، هزینه‌ی نگهداری از یک ایستگاه اتوبوس آمده است.($1\leq n \leq 10^6$ و $1\leq c \leq 10^9$)

سطر دوم شامل $n$ عدد صحیح $x_1,x_2,…,x_n$ است به طوری که $x_i$ مکان خانه‌ی کارمند $i$- ام را نشان می‌دهد.($-10^9 \leq x_1,x_2,…,x_n\leq 10^9$)

خروجی

درتنها سطر خروجی هزینه‌ای که کارخانه باید برای رفت و آمد روزانه بپردازد را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4 100
20 10 40 30
100
6 10
-51 -49 -1 1 49 51
36

شرح ورودی و خروجی نمونه

در ورودی نمونه‌ی اول، به دلیل هزینه‌ی زیاد ایستگاه اتوبوس، حالت بهینه این است که همه‌ی کارمندان تنها از تاکسی استفاده کنند در این صورت هزینه برابر می‌شود با : $10+20+30+40=100$.

در ورودی نمونه دوم، یکی از حالت‌های بهینه ساخت سه ایستگاه اتوبوس در مکان‌های ۵۰-، ۰ و ۵۰ است، در این صورت کارمندان در مجموع با ۳۶ تومان به مقصدهایشان می‌رسند.


ابزار صفحه