Mã C ++ để tìm k tối thiểu để nhận được nhiều phiếu bầu từ sinh viên

Giả sử chúng ta có một mảng A với n phần tử. Có n học sinh trong một trường và mỗi học sinh có đúng k phiếu bầu và tất cả các phiếu bầu nên được sử dụng. Có hai bên. A [i] đại diện cho học sinh thứ i đã cho A [i] số phiếu bầu cho bên thứ nhất và điều này ngụ ý rằng bên thứ hai sẽ nhận được k- A [i] số phiếu bầu. Bên thứ hai muốn đặt k theo cách mà họ thắng. Giá trị nhỏ nhất có thể có của k sẽ là bao nhiêu.

Vì vậy, nếu đầu vào là A =[2, 2, 3, 2, 2], thì đầu ra sẽ là 5, bởi vì bên thứ nhất nhận được 2 + 2 + 3 + 2 + 2 =11 phiếu bầu. nếu k =5, thì bên thứ hai sẽ nhận được 3 + 3 + 2 + 3 + 3 =14 phiếu và thắng cuộc bầu cử.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

{ 2, 2, 3, 2, 2 }

Đầu ra

5