Fill the Containers

توسط علیرضا رضایی نیا

ارسال شده در
1397-03-03

Fill the Containers

شرح سوال


سوالی که امروز مورد بررسی قرار میدیم سوال uva-11413 است...سوال میگه ما یه چند تا بشکه داریم که داخلش شیره... حالا میگه ما یه چند تا ظرف داریم میخوایم این ظرفارو تا لبه پر شیر کنیم.توجه کنید که برای ور کردن ظرف باید به ترتیبی که سوال میده ظرفو پر کنید.یعنی مثلا نمیتونید از بشکه ۱ و بشکه ۵ بریزید تو ظرف مثلا۱ . باید بشکه یکو وقتی ریختید تو ظرف بعد برید سراغ بشکه دومی .این ظرف ها را هر گنجایشی که دلتون میخواد میتونید بگیرید(نامحدود). حالا میگه طوری عمل کنید که ظرفیت ظرف مینیمم باشه حالا از این مینیمم ها ماسیمم مقداری که ظرف میگیره رو چاپ کنید.یعنی چی؟ بیاین یک مثال بزنیم.(مثال خود سوال)

ما مثلا سه تا ظرف داریم و پتج تا بشکه که داخلشون به ترتیب 1 2 3 4 5 لیتر شیره .خب جواب بهینه به این صورت است در ظرف اول ۱ و ۲و ۳ میریزیم که میشه ۶ لیتر در ظرف دوم ۴ لیتر و در ظرف سوم پنج لیتر و ماکزیمم میشه ۶ لیتر.چرا این جواب بهینه است؟ حالات دیگه رو چک کن ببین ماکزیممش از ۶ کمتره یا بیشتر!

بیایید فرض کنیم ظریف ظرف هایی ک میگیریم یکسان باشد .مشکلی به وجود میآید؟ خیر مثلا در مثال قبلی ظرفیت ظرف ها همه ۶ باشه . بریم سراغ حل سوال.

ما باید هر بار  یک مقدار از بین اون محمدوده ای که داده (۱تا۱۰۰۰۰۰۰۰۰۰) انتخاب کنیم و سپس برا اون چک کنیم ببینیم اگر میتونستیم ظرفیتو کمتر کنیم که کمتر میکنی(حالتی که همه مقدار شیر را بتوانیم در ظرف بریزیم) اگرم نه که زیاد کنیم(حالتی که شیر از ظرفیت ظرف بیشتر شود یا حالتی که تعداد ظرف های مورد نیاز بیشتر از تعداد ظرفی که داریم بشود)که این کار با یک باینری سرچ حل میشود.


توضیحات


سطح سوال لینک سوال
متوسط Fill the Containers

کد حل سوال


حل سوال به زبان:
سی پلاس پلاس java وجود ندارد python وجود ندارد

دانلود حل سوال


PDF

تگ ها:
binary search
شما برای ارسال نظر باید وارد سایت شوید

جستجو در سایت

به کانال تلگرامی ما بپیوندید