Tìm k nhỏ nhất để phe 2 thắng cử bằng C++

Mô tả bài toán

Có n học sinh, mỗi người có k phiếu bầu (phải dùng hết). Học sinh i bỏ A[i] phiếu cho phe 1, phần còn lại (k - A[i]) cho phe 2. Phe 2 muốn chọn k nhỏ nhất sao cho tổng phiếu phe 2 > tổng phiếu phe 1.

Ví dụ

A = [2,2,3,2,2] → Tổng phe 1 = 11. Với k=5: phe 2 được 3+3+2+3+3 = 14 → thắng. Output: 5.

Thuật toán

Tổng phiếu phe 1 = S. Tổng phiếu phe 2 = n*k - S. Điều kiện: n*k - S > S → k > 2*S/n. k phải là nguyên và ≥ max(A). Do đó k = max(max(A), floor(2*S/n) + 1).

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int n = A.size();
    long long sum = 0;
    int mx = 0;
    for (int x : A) {
        sum += x;
        mx = max(mx, x);
    }
    return max(mx, (int)(2 * sum / n + 1));
}

int main() {
    vector<int> A = {2,2,3,2,2};
    cout << solve(A) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: {2,2,3,2,2}

Output: 5