মনে করুন আমাদের কাছে একটি মান n এবং restrictions নামে জোড়ার একটি তালিকা আছে। আমরা একটি শহরে n নতুন বিল্ডিং বানাতে চাই। কিন্তু কিছু সীমাবদ্ধতা আছে। আমরা এক লাইনে বানাতে পারি এবং বিল্ডিংগুলো 1 থেকে n পর্যন্ত লেবেল করা আছে। restrictions-এর দুটি প্যারামিটার আছে, restrictions[i] = (id_i, max_height_i) নির্দেশ করে id_i-র হাইট max_height_i-র চেয়ে বেশি হবে না। নতুন বিল্ডিংগুলোর হাইটের উপর শহরের সীমাবদ্ধতাগুলো নিচের মতো −
প্রতিটি বিল্ডিংর হাইট 0 বা পজিটিভ মান হতে হবে।
প্রথম বিল্ডিংর হাইট অবশ্যই 0 হতে হবে।
যে কোনো দুটি সন্নিহিত বিল্ডিংর হাইটের পার্থক্য 1-র চেয়ে বেশি হতে পারবে না।
আমাদের সবচেয়ে উঁচু বিল্ডিংর সর্বোচ্চ সম্ভাব্য হাইট বের করতে হবে।
সুতরাং, যদি ইনপুট হয় n = 5, restrictions = [[2,1],[4,3]], তবে আউটপুট হবে 4 কারণ আমাদের সর্বোচ্চ সম্ভাব্য হাইট বের করতে হবে, যা ডায়াগ্রামে দেখা যাচ্ছে 4।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব −
যদি restrictions খালি হয়, তবে
n-1 রিটার্ন করুন
resi := restrictions তালিকাটি id অনুযায়ী সর্ট করুন
k := 0
idx := 1
resi-এ প্রতিটি re-এর জন্য, করুন
re[1] := re[1] এবং (k+re[0]-idx) এর মধ্যে ন্যূনতম
k := re[1]
idx := re[0]
k := resi-এর লাস্ট এলিমেন্টের ম্যাক্স হাইট
idx := resi-এর লাস্ট এলিমেন্টের আইডি
resi তালিকাটি রিভার্স করুন
resi-এর প্রথম আইটেম থেকে শুরু করে প্রতিটি re-এর জন্য, করুন
re[1] := re[1] এবং (k-re[0]+idx) এর মধ্যে ন্যূনতম
k := re[1]
idx := re[0]
resi তালিকাটি রিভার্স করুন
f := 0
idx := 1
res := 0
resi-এ প্রতিটি re-এর জন্য, করুন
ff := (f+re[0]-idx) এবং re[1] এর মধ্যে ন্যূনতম
res := res এবং (re[0] - idx + f + ff)/2-এর ভাগফলের মধ্যে সর্বোচ্চ
idx := re[0]
f := ff
(f+n-idx) এবং res-এর মধ্যে সর্বোচ্চ রিটার্ন করুন
উদাহরণ
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন
def solve(n, restrictions):
if not restrictions:
return n-1
resi = sorted(restrictions, key=lambda x:x[0])
k = 0
idx = 1
for re in resi:
re[1] = min(re[1], k+re[0]-idx)
k = re[1]
idx = re[0]
k = resi[-1][1]
idx = resi[-1][0]
resi.reverse()
for re in resi[1:]:
re[1] = min(re[1], k-re[0]+idx)
k = re[1]
idx = re[0]
resi.reverse()
f = 0
idx = 1
res = 0
for re in resi:
ff = min(f+re[0]-idx, re[1])
res = max(res, (re[0] - idx + f + ff) // 2)
idx = re[0]
f = ff
return max(f+n-idx, res)
n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))
ইনপুট
5, [[2,1],[4,3]]
আউটপুট
4
