समस्या
सभी मशीनें समय 0 पर शुरू होती हैं और स्वतंत्र रूप से काम करती हैं। किसी मशीन को एक वस्तु बनाने में t सेकंड लगते हैं, वह t सेकंड बाद एक वस्तु, 2t सेकंड बाद दूसरी वस्तु, और इसी तरह बनाती है। जब सभी मशीनों का कुल उत्पादन लक्ष्य तक पहुँच जाए, तब तक का सबसे कम पूर्णांक सेकंड ज्ञात करें।
factory_machines(times, target) को इम्प्लीमेंट करें।
इनपुट
times: प्रत्येक मशीन को एक वस्तु बनाने में लगने वाले सेकंड।
target: आवश्यक पूर्ण वस्तुओं की संख्या।
आउटपुट
कुल बीते हुए न्यूनतम सेकंड लौटाएँ।
सीमाएँ
1 ≤ machines ≤ 200,000. प्रत्येक time और target 1 और 1,000,000,000 के बीच हैं। उत्तर signed 64-bit में फिट होता है।
उदाहरण
इनपुट:
times = [2, 3]
target = 5
अपेक्षित आउटपुट:
expected = 6इनपुट:
std::vector<long long> times = {2, 3};
long long target = 5;
अपेक्षित आउटपुट:
long long expected = 6;इनपुट:
long[] times = new long[] {2, 3};
long target = 5;
अपेक्षित आउटपुट:
long expected = 6;व्याख्या
समय 6 पर मशीनों ने 3 + 2 = 5 वस्तुएँ बना ली हैं। समय 5 पर केवल 2 + 1 = 3 वस्तुएँ बनी हैं।
इनपुट:
times = [4]
target = 3
अपेक्षित आउटपुट:
expected = 12इनपुट:
std::vector<long long> times = {4};
long long target = 3;
अपेक्षित आउटपुट:
long long expected = 12;इनपुट:
long[] times = new long[] {4};
long target = 3;
अपेक्षित आउटपुट:
long expected = 12;व्याख्या
एक मशीन अपनी तीसरी वस्तु 3 × 4 = 12 सेकंड में पूरी करती है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
किसी चुने हुए time पर count करो कि सभी machines मिलकर तब तक कितने items बना लेंगी.
संकेत 2
Answer वह earliest time है जब produced count target तक पहुँच जाए.
संकेत 3
ऐसी monotonic condition को production simulate करने की बजाय time पर search करना बेहतर है.
अपेक्षित जटिलता
समय O(n log T), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।