मान लीजिए हमारे पास n तत्वों की एक सरणी A है। एक स्कूल में n छात्र हैं और उनमें से प्रत्येक के पास ठीक k वोट हैं और सभी वोटों का उपयोग किया जाना चाहिए। दो पार्टियां हैं। A[i] दर्शाता है कि iवें छात्र ने पहली पार्टी को A[i] मात्रा में वोट दिए हैं और इसका तात्पर्य है कि दूसरी पार्टी को k - A[i] वोट मिलेंगे। दूसरी पार्टी k को इस तरह सेट करना चाहती है कि वे जीतें। k का न्यूनतम संभव मान क्या होगा।
उदाहरण के लिए, यदि इनपुट A = [2, 2, 3, 2, 2] है, तो आउटपुट 5 होगा, क्योंकि पहली पार्टी को 2 + 2 + 3 + 2 + 2 = 11 वोट मिल रहे हैं। यदि k = 5, तो दूसरी पार्टी को 3 + 3 + 2 + 3 + 3 = 14 वोट मिलेंगे और चुनाव जीत जाएगी।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := size of A for initialize k := 0, when k < n, update (increase k by 1), do: x := A[k] m := maximum of m and x s := s + x return maximum of m and (2 * s / n + 1)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#includeusing namespace std; int solve(vector A){ int n = A.size(), k = 0, s = 0, m = 0; for (int k = 0; k < n; k++){ int x = A[k]; m = max(m, x); s += x; } return max(m, 2 * s / n + 1); } int main(){ vector A = { 2, 2, 3, 2, 2 }; cout << solve(A) << endl; }
इनपुट
{ 2, 2, 3, 2, 2 }आउटपुट
5