छात्रों से अधिक वोट प्राप्त करने के लिए न्यूनतम k खोजने के लिए C++ कोड

मान लीजिए कि हमारे पास n तत्वों के साथ एक सरणी A है। एक स्कूल में n छात्र हैं और उनमें से प्रत्येक के पास ठीक k वोट हैं और सभी वोटों का उपयोग किया जाना चाहिए। दो पार्टियां हैं। A[i] प्रतिनिधित्व करता है कि ith छात्र ने A[i] को पहली पार्टी को वोटों की राशि दी है और इसका मतलब है कि दूसरे पक्ष को k-A[i] वोटों की संख्या मिलेगी। दूसरा पक्ष k को इस प्रकार सेट करना चाहता है कि वह जीत जाए। k का न्यूनतम संभव मान क्या होगा।

तो, अगर इनपुट ए =[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)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> 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<int> A = { 2, 2, 3, 2, 2 };
   cout << solve(A) << endl;
}

इनपुट

{ 2, 2, 3, 2, 2 }