मान लीजिए कि हमारे पास ढेर नामक संख्याओं की एक सूची है और एक मान k है। ढेर [i] ढेर पर पत्थरों की संख्या का प्रतिनिधित्व करता है i। प्रत्येक घंटे में, हम किसी ढेर का चयन करते हैं और उस ढेर से r संख्या में पत्थरों को हटाते हैं। यदि हम r से कम पत्थरों वाला ढेर चुनते हैं, तब भी ढेर को साफ करने में एक घंटे का समय लगता है। हमें r का न्यूनतम मान ज्ञात करना होगा, ताकि हम सभी पत्थरों को k घंटे से कम या उसके बराबर में हटा सकें।
इसलिए, यदि इनपुट पाइल्स की तरह है =[3, 6, 4] k =5, तो आउटपुट 3 होगा, क्योंकि, r =3 स्टोन्स प्रति घंटे के लिए, हम दूसरे पाइल को 2 घंटे में साफ़ कर सकते हैं, फिर साफ़ करें 2 घंटे में तीसरा, और पहला ढेर 1 घंटे में साफ़ करें।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एल :=1
- h :=अधिकतम बवासीर
- r :=h
- एक फंक्शन टर्न्स () को परिभाषित करें। इसमें r लगेगा
- सूची में मौजूद सभी तत्वों का रिटर्न योग (बवासीर में प्रत्येक बी के लिए बी / आर की छत)
- मुख्य विधि से, निम्न कार्य करें -
- जबकि एल <एच, करते हैं
- मध्य :=(एल + एच) / 2 की मंजिल
- यदि मुड़ता है (मध्य)> k, तो
- l :=मध्य + 1
- अन्यथा,
- ज :=मध्य
- r :=न्यूनतम r और मध्य
- रिटर्न आर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
from math import ceil def solve(piles, k): l = 1 h = max(piles) r = h def turns(r): return sum(ceil(b / r) for b in piles) while l < h: mid = (l + h) // 2 if turns(mid) > k: l = mid + 1 else: h = mid r = min(r, mid) return r piles = [3, 6, 4] k = 5 print(solve(piles, k))
इनपुट
[3, 6, 4], 5
आउटपुट
3