فهرست مندرجات
Rabbits
علی $n$ خرگوش دارد و می‌خواهد از شهر A به شهر B برود.
خرگوش $i$ ام $w_i$ کیلوگرم وزن دارد و هزینه حمل یک متر هر کیلوگرم خرگوش برابر با $k$ است. همچنین بین دو شهر A و B ، $n$ شهر وجود دارد که فاصله شهر $i$ ام از شهر A برابر $d_i$ متر است.
در شهر $i$ ام هر کیلو خرگوش را به قیمت $p_i$ خریداری می‌کنند.
علی می‌خواهد $n$ خرگوش خود را در مسیر بفروشد طوری که در هر شهر دقیقاً یکی از آن‌ها را بفروشد. شما باید مشخص کنید که علی باید در هر شهر چه خرگوشی را بفروشد تا هزینه‌ای که به‌دست می‌آورد بیشینه باشد.
ورودی
- در سطر اول ورودی دو عدد $1 \leq n \leq 1000$ و $1 \leq k \leq 10^9$ آمده است .
- در سطر بعدی $n$ عدد $w_1$ تا $w_n$ آمده است.
- در سطر بعدی $n$ عدد $d_1$ تا $d_n$ آمده است.
- در سطر بعدی $n$ عدد $p_1$ تا $p_n$ آمده است.
خروجی
در تنها سطر خروجی $n$ عدد $r_1$ تا $r_n$ را چاپ کنید که نشان می‌دهد علی باید در شهر $i$ ام خرگوش $r_i$ را بفروشد.
محدودیت‌ها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودي و خروجي نمونه
| ورودي نمونه | خروجي نمونه |
|---|---|
| 3 1 10 20 15 10 20 30 50 70 60 | 3 2 1 |
پاسخ
راه‌حل این سوال greedy (حریصانه) است. نکته کلیدی در حل سؤال این است که اگر $1$ کیلوگرم خرگوش در شهر $i$ ام فروخته شود مقدار سود ما از آن ثابت و مستقل از باقی و برابر با ($p_i + d_i -k$) است که آن را ارزش آن شهر می‌نامیم. تنها محدودیت این است که یک خرگوش باید به طور کامل در یک شهر و در هر شهر فقط یک خرگوش فروخته شود. راه حل حریصانه بدین صورت است که شهرها را بر اساس ارزش و خرگوش‌ها را بر اساس وزن (هر دو از بزرگ به کوچک) مرتب کرده و به ترتیب با هم جفت کرده. پیچیدگی الگوریتم هم برابر با $O(n \log n)$ است که مربوط به مرتب کردن است.
برای اثبات الگوریتم فرض کنید که جواب ما بهینه نباشد. جواب ما و بهینه را در نظر می‌گیریم و هر دو را بر حسب ارزش شهرها مرتب کرده (هر دو از بزرگ به کوچک) و اولین جایی که با هم فرق دارن را در نظر بگیرید. خرگوشی که با این شهر در جواب بهینه جور شده $a$ و در جواب ما $b$ می‌نامیم. وزن $b > a$ است. اگر در جواب بهینه جای $b$ ، $a$ را عوض کنیم به اندازه $b-a$ ارزش این شهر سود می‌کنیم پس می توان این $2$ رو با هم عوض کرد و جواب بهینه‌تر شود.
تناقض!
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
