मान लीजिए हमारे पास n तत्वों वाला एक सरणी A और एक अन्य संख्या k है। मान लें कि एक प्रतियोगिता में n समस्याएं हैं। अमल की समस्या सुलझाने की क्षमता k है। अमल हमेशा सूची के किसी भी छोर से समस्या हल करता है। और वह उस समस्या को हल नहीं कर सकता जिसकी कठिनाई k से अधिक है। वह तब रुकता है जब बाएं और दाएं समस्याओं की कठिनाई k से अधिक होती है। हमें गिनना है कि वह कितनी समस्याएं हल कर सकता है। A[i] i-वें समस्या की कठिनाई को दर्शाता है।
उदाहरण के लिए, यदि इनपुट A = [4, 2, 3, 1, 5, 1, 6, 4]; k = 4 है, तो आउटपुट 5 होगा, क्योंकि प्रारंभ में बाएं से 4 कठिनाई वाली समस्या हल करता है, फिर दाएं से 4 कठिनाई वाली समस्या, फिर दाएं से और नहीं हल कर सकता, फिर बाएं से, 2, 3 और 1 कठिनाई वाली समस्याएं हल करता है। कुल 5 समस्याएं हल की जा सकती हैं।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := size of A l := 0 r := n - 1 for initialize i := 0, when i < n, update (increase i by 1), do: if A[i] <= k and l is same as i, then: (increase l by 1) while A[r] <= k, do: (decrease r by 1) if l is same as n, then: return n Otherwise return n - 1 - r + l
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A, int k) { int n = A.size(); int l = 0, r = n - 1; for (int i = 0; i < n; ++i) { if (A[i] <= k && l == i) ++l; } while (A[r] <= k) --r; if (l == n) return n; else return n - 1 - r + l; } int main() { vector<int> A = { 4, 2, 3, 1, 5, 1, 6, 4 }; int k = 4; cout << solve(A, k) << endl; }
इनपुट
{ 4, 2, 3, 1, 5, 1, 6, 4 }, 4
