학생들로부터 더 많은 표를 얻기 위해 최소 k를 찾는 C++ 코드

<시간/>

n개의 요소가 있는 배열 A가 있다고 가정합니다. 한 학교에 n명의 학생이 있고 각 학생은 정확히 k표를 가지며 모든 표를 사용해야 합니다. 두 당사자가 있습니다. A[i]는 i번째 학생이 A[i]만큼의 표를 제1당에 주었다는 것을 나타내며 이는 두 번째 정당이 k-A[i]의 표를 얻음을 의미합니다. 두 번째 당사자는 k를 승리하는 방식으로 설정하려고 합니다. k의 가능한 최소값은 얼마가 될까요?

따라서 입력이 A =[2, 2, 3, 2, 2]와 같으면 첫 번째 정당이 2 + 2 + 3 + 2 + 2 =11표를 얻었기 때문에 출력은 5가 됩니다. 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 }