รหัส C++ เพื่อค้นหา k ขั้นต่ำเพื่อรับคะแนนโหวตเพิ่มเติมจากนักเรียน

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

ดังนั้นหากอินพุตเป็น A =[2, 2, 3, 2, 2] ผลลัพธ์จะเป็น 5 เพราะพรรคแรกได้ 2 + 2 + 3 + 2 + 2 =11 โหวต ถ้า 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 }