बड़े सरणी में [currPos] से [currPos - k] तक अधिकतम गणना

Question

मैं एसीएम प्रतियोगिता की तैयारी कर रहा हूं और मैं इस समस्या से फंस गया हूं।

आप दी गई स्थिति क्सी और ऊंचाई हाय ढाल स्टील के बने होते साथ इमारतें हैं और वे एक ही ऊंचाई के साथ कम से कम दो इमारतों द्वारा समर्थित होने की जरूरत है। ढाल का सही अंत कुछ भवन के शीर्ष पर होना चाहिए। ढाल के नीचे स्थित सभी इमारतों (अंत में झूठ बोलने वालों सहित) को उस ढाल से संरक्षित किया जाता है और उनकी ऊंचाई उस ऊंचाई से अधिक नहीं हो सकती जिस पर ढाल लगाई जाती है। एक इमारत को एक ढाल पर संरक्षित किया जा सकता है।

आपको असीमित संख्या में ढाल दी जाती है, प्रत्येक एक ही लंबाई के साथ एल। ढाल द्वारा संरक्षित की जा सकने वाली इमारतों की अधिकतम संख्या पाएं और न्यूनतम संख्या में ढाल ढूंढें जिनका उपयोग भवनों की अधिकतम संख्या की रक्षा के लिए किया जा सकता है ।

इनपुट

इनपुट की पहली पंक्ति एक सकारात्मक पूर्णांक टी (1 < = टी < = 20), परीक्षण के मामलों की संख्या में शामिल है।

प्रत्येक परीक्षण का मामला एक लाइन है कि वास्तव में दो पूर्णांकों शामिल साथ शुरू होता है: भवनों की संख्या एन (2 < = एन < = 100,000) और एक ढाल एल (1 < = एल < = 1,000,000,000) की लंबाई। अगली एन लाइनों में से प्रत्येक में दो पूर्णांक होते हैं, शी (आई-वें भवन की स्थिति,= शी < = 1,000,000,000) और हाय (आई-वें भवन की ऊंचाई, 1 < = हाय < = 1,000,000,000)। इमारतों को उनके एक्स समन्वय द्वारा क्रमबद्ध दिया जाता है। एक ही एक्स समन्वय के साथ दो इमारतें नहीं होंगी।

आउटपुट

प्रत्येक परीक्षा मामले के लिए, पर दो एक पंक्ति, उत्पादन इमारतों की अधिकतम संख्या है कि कवर किया जा सकता और ढाल है कि उस उद्देश्य के लिए इस्तेमाल किया जा सकता की न्यूनतम संख्या।

उदाहरण

Input 
17 3 
1 2 
2 1 
3 2 
4 3 
5 1 
6 2 
7 4 
8 2 
9 3 
10 4 
11 2 
15 2 
16 1 
17 3 
18 3 
19 1 
20 2 

Output 
11 3 

Explanation: 
first shield: 1,2,3 
second shield: 7,8,9,10 
third shield: 15,16,17,18 

जाहिर जानवर बल समाधान कोड के लिए आसान कोड है, लेकिन समय सीमा (1s), मैं खंड पेड़ के बारे में पढ़ रहा था पर विफल हो जाएगा, लेकिन जब से मैं काम नहीं किया सेगमेंट ट्री के साथ मुझे दिलचस्पी है कि इस समस्या को हल करने का तरीका या क्या कोई आसान समाधान है जिसे मैं याद कर रहा हूं?

पीएस हालांकि यह कहता है कि ढाल लंबाई एल है, यह वास्तव में एल + 1 है, आखिरी इमारत उच्चतम होनी चाहिए और एक शील्ड रखने में सक्षम होने के लिए स्थिति [Xi-1, Xi-L] पर एक इमारत होनी चाहिए और निर्माण की स्थिति को हल किया जाएगा।

Answer 1

pos - k से pos से अधिकतम ढूँढना "स्लाइडिंग विंडो अधिकतम समस्या" के रूप में भी जाना जाता है और इसमें सेगमेंट पेड़ या किसी भी अन्य उन्नत डेटा संरचनाओं के बिना O(N) समाधान सरल है।
एल्गोरिदम निम्न है:
1) चलो <value, position> जोड़े के deque बनाए रखें।

//Moving the right border. 
right <- right + 1 
cur <- pair<value[right], x[right]> 
while not deque.empty and deque.back.value < cur.value 
    deque.pop_back() 
deque.push_back(cur) 

//Moving the left border. 
left <- left + 1 
while deque.front.position is out of [x[left], x[right]] bounds 
    deque.pop_front() 

3) अधिकतम बस deque.front.value है:
2) खिड़की सीमा चलती निम्नलिखित तरीके से किया जाता है (मैं यहाँ छद्म कोड) का उपयोग करें।

इस एल्गोरिथ्म की जटिलता O(N) क्योंकि प्रत्येक तत्व केवल एक बार Deque को धक्का दे दिया जाता है और यह इसे से केवल एक बार निकाल दिया जाता है (और छद्म कोड में while पाश से प्रत्येक यात्रा से ऊपर Deque से एक तत्व को हटाता है) है।

अब ढाल के बारे में मूल समस्या का समाधान:
1) के dp[pos] मान लेते हैं = जोड़ी < कवर इमारतों की अधिकतम संख्या, ढाल की न्यूनतम संख्या का इस्तेमाल किया > ऐसी है कि सब ढाल 'सही सीमा < = pos है।
2) चलो दो पॉइंटर्स low और high बनाए रखें। high वर्तमान भवन के लिए एक सूचक है और low पॉइंटर बाएं भवन के लिए एक सूचक है जैसे कि x[high] - x[low] >= L।
3) high पॉइंटर हमेशा for लूप में से एक द्वारा बढ़ाया जाता है और low पॉइंटर उचित रूप से समायोजित किया जाता है (2 को संतुष्ट करने के लिए) संपत्ति।
4) तो फिर dp निम्नलिखित तरीके से गणना की जा सकती: high की एक निश्चित मूल्य के लिए, dp[high] या तो dp[high - 1] या dp[low - 1] + high - low + 1 (दूसरा प्रयोग किया जाता है, तभी आप उसे high को low से एक ढाल जगह के लिए संभव है) है।
5) यह कैसे जांचें कि ढाल लगाने के लिए संभव है? स्लाइडिंग विंडो अधिकतम एल्गोरिदम का उपयोग करके, [low; high - 1] रेंज में अधिकतम मान को बनाए रखना संभव है और जांचें कि यह H[high] के बराबर है या नहीं।
6) उत्तर dp[N - 1] (0-आधारित अनुक्रमण के साथ) है।

इस समाधान की जटिलता O(N) क्योंकि low और high हमेशा बढ़ती है, और वे एक से अधिक N बार वृद्धि नहीं की जा सकती और स्लाइडिंग खिड़की अधिकतम एल्गोरिथ्म जटिलता ऊपर दिखाया गया था है।