পাইথনে গ্রাম্পি বুকস্টোর ওনার সমস্যা

মনে করুন একটি বুকস্টোর ওনার দোকান খোলেন থাকে customers লিস্টের লেন্থ মিনিট। প্রতিটি মিনিটে কিছু গ্রাহক (customers[i]) ঢুকেন, এবং সেই মিনিটের শেষে সবাই চলে যায়। কিছু মিনিটে ওনার গ্রাম্পি (রুঝে) থাকেন। grumpy[i] = 1 মানে i-তম মিনিটে ওনার গ্রাম্পি, 0 মানে না। ওনার গ্রাম্পি থাকলে সে মিনিটের গ্রাহকগণ অদুঃখী, অন্যথায় সুখী। ওনার একটি টেকনিক জানেন যাতে সে X মিনিট সরাসরি গ্রাম্পি না থাকেন। এই টেকনিক একবারের বেশি ব্যবহার করা যাবে না। আমাদের সর্বোচ্চ কতজন গ্রাহক দিনভর সুখী থাকতে পারে সেটি বের করতে হবে।

ইনপুট: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 হলে আউটপুট 16। কারণ ওনার শেষ তিন মিনিট গ্রাম্পি থাকবেন না। তাই সুখী গ্রাহক: 1+1+1+1+7+5 = 16।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব (স্লাইডিং উইন্ডো):

i := 0, j := 0, sums := [], temp := 0
while j - i + 1 < X:
- যদি grumpy[j] == 1, তবে temp += customers[j]
- j++
sums.append([temp, i, j])
i++, j++
while j < len(customers):
- যদি grumpy[i-1] == 1, তবে temp -= customers[i-1]
- যদি grumpy[j] == 1, তবে temp += customers[j]
- sums.append([temp, i, j])
- i++, j++
sums প্রথম এলিমেন্ট অনুযায়ী সর্ট করুন।
index1 := sums[-1][1], index2 := sums[-1][2]
for i in range(index1, index2+1): grumpy[i] = 0
ans := 0
for i in range(len(customers)):
- যদি grumpy[i] == 0, তবে ans += customers[i]
return ans

উদাহরণ

class Solution(object):
    def maxSatisfied(self, customers, grumpy, X):
        i = 0
        j = 0
        sums = []
        temp = 0
        while j - i + 1 < X:
            if grumpy[j]:
                temp += customers[j]
            j += 1
        sums.append([temp, i, j])
        i += 1
        j += 1
        while j < len(customers):
            if grumpy[i-1]:
                temp -= customers[i-1]
            if grumpy[j]:
                temp += customers[j]
            sums.append([temp, i, j])
            i += 1
            j += 1
        sums = sorted(sums, key=lambda v: v[0])
        index1 = sums[-1][1]
        index2 = sums[-1][2]
        for i in range(index1, index2+1):
            grumpy[i] = 0
        ans = 0
        for i in range(len(customers)):
            if not grumpy[i]:
                ans += customers[i]
        return ans

ob = Solution()
print(ob.maxSatisfied([1,0,1,2,1,1,7,5], [0,1,0,1,0,1,0,1], 3))

ইনপুট

[1,0,1,2,1,1,7,5] [0,1,0,1,0,1,0,1] 3