学生からより多くの票を得るために最小kを見つけるためのC++コード

n個の要素を持つ配列Aがあるとします。学校にはn人の生徒がいて、それぞれが正確にk票を持っているので、すべての票を使用する必要があります。 2つのパーティがあります。 A [i]は、i番目の学生が最初のパーティにA [i]の票を与えたことを表します。これは、2番目のパーティがk-A[i]の票を獲得することを意味します。 2番目のパーティは、勝つようにkを設定したいと考えています。 kの可能な最小値は何になりますか。

したがって、入力がA =[2、2、3、2、2]の場合、最初のパーティは2 + 2 + 3 + 2 + 2 =11票を獲得しているため、出力は5になります。 k =5の場合、2番目の政党は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 }

出力

5