मान लीजिए हमारे पास आकार n की दो सरणी A, और आकार m की B, और एक अन्य संख्या r है। शेयर खरीदने के n अवसर हैं। iवां अवसर हमें जितने चाहें उतने शेयर खरीदने की अनुमति देता है, iवें शेयर की कीमत A[i] है। और शेयर बेचने के m अवसर भी हैं। iवां अवसर हमें जितने चाहें उतने शेयर बेचने की अनुमति देता है, iवें शेयर की बिक्री कीमत B[i] है। हम अपने पास मौजूद शेयरों से अधिक नहीं बेच सकते। यदि हमारे पास r राशि का पैसा है और कोई मौजूदा शेयर नहीं है, तो हमें खरीदने और बेचने के बाद हमारे पास रखे जा सकने वाले पैसे की अधिकतम राशि ढूंढनी है।
उदाहरण के लिए, यदि इनपुट A = [4, 2, 5]; B = [4, 4, 5, 4]; r = 11 है, तो आउटपुट 26 होगा, क्योंकि हमारे पास 11 राशि का पैसा है। 2 की कीमत पर 5 शेयर खरीदना इष्टतम है, और फिर उन सभी को 5 की कीमत पर बेचना। इस प्रकार हम अंत में 26 प्राप्त कर सकते हैं।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := size of A an := 1100 bn := 0 for initialize i := 0, when i < n, update (increase i by 1), do: if an > A[i], then: an := A[i] for initialize i := 0, when i < m, update (increase i by 1), do: if bn < B[i], then: bn := B[i] if bn > an, then: r := bn * (r / an) + (r - (r / an) * an) return r
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(vector A, vector B, int r){ int n = A.size(), m = B.size(); int an = 1100, bn = 0; for (int i = 0; i < n; i++){ if (an > A[i]) an = A[i]; } for (int i = 0; i < m; i++){ if (bn < B[i]) bn = B[i]; } if (bn > an){ r = (bn) * (r / an) + (r - (r / an) * an); } return r; } int main(){ vector A = { 4, 2, 5 }; vector B = { 4, 4, 5, 4 }; int r = 11; cout << solve(A, B, r) << endl; }
इनपुट
{ 4, 2, 5 }, { 4, 4, 5, 4 }, 11आउटपुट
26
