ছাত্রদের থেকে বেশি ভোট পেতে ন্যূনতম k খুঁজে পেতে C++ কোড

ধরুন আমাদের n উপাদান সহ একটি অ্যারে A আছে। একটি স্কুলে n ছাত্র আছে এবং তাদের প্রত্যেকের ঠিক k ভোট আছে এবং সমস্ত ভোট ব্যবহার করা উচিত। দুটি দল আছে। এ দ্বিতীয় দলটি এমনভাবে 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)

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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 }