علی $n$ خرگوش دارد و میخواهد از شهر A به شهر B برود.
خرگوش $i$ ام $w_i$ کیلوگرم وزن دارد و هزینه حمل یک متر هر کیلوگرم خرگوش برابر با $k$ است. همچنین بین دو شهر A و B ، $n$ شهر وجود دارد که فاصله شهر $i$ ام از شهر A برابر $d_i$ متر است.
در شهر $i$ ام هر کیلو خرگوش را به قیمت $p_i$ خریداری میکنند.
علی میخواهد $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$ رو با هم عوض کرد و جواب بهینهتر شود.
تناقض!