โค้ด C++ หาค่า k ต่ำสุดเพื่อให้พรรคที่สองชนะ

สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ มีนักเรียน n คนในโรงเรียน แต่ละคนมีโหวต k โหวต และต้องใช้โหวตทั้งหมด มีสองพรรค A[i] แทนว่า นักเรียนคนที่ i โหวตให้พรรคแรก A[i] โหวต หมายความว่าพรรคที่สองจะได้ k - A[i] โหวต พรรคที่สองต้องการตั้งค่า k ให้พวกเขาชนะ ค่า k ต่ำสุดที่เป็นไปได้คือเท่าไหร่

เช่น ถ้าอินพุตคือ A = [2, 2, 3, 2, 2] เอาต์พุตจะเป็น 5 เพราะพรรคแรกได้ 11 โหวต ถ้า k = 5 พรรคที่สองจะได้ 14 โหวตและชนะ

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
for k := 0 ถึง n-1:
    x := A[k]
    m := max(m, x)
    s := s + x
return max(m, 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 }