การเลือกตั้งออนไลน์ในภาษา C++

สมมติว่าในการเลือกตั้ง การลงคะแนนครั้งที่ i- ใช้สำหรับบุคคล[i] ในช่วงเวลา[i] ตอนนี้ เราต้องใช้ฟังก์ชันแบบสอบถามต่อไปนี้:TopVotedCandidate.q(int t) สิ่งนี้จะค้นหาจำนวนบุคคลที่เป็นผู้นำการเลือกตั้ง ณ เวลา t การลงคะแนนเสียงในเวลา t จะนับรวมกับข้อความค้นหาของเรา หากเสมอกัน การโหวตล่าสุด (ในหมู่ผู้สมัครที่เสมอกัน) จะเป็นผู้ชนะ

ดังนั้นหากเราเริ่มต้นสิ่งนี้ด้วย TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]) ให้เรียก q() like:q( 3), q(12), q(25), q(15), q(24), q(8) จากนั้นผลลัพธ์จะเป็น [0, 1, 1, 0, 0, 1] สำหรับการเรียกแต่ละครั้ง q(). เนื่องจาก ณ เวลาที่ 3 คะแนนโหวตคือ [0] และ 0 เป็นผู้นำ ณ เวลาที่ 12 คะแนนโหวตคือ [0,1,1] และที่นี่ 1 เป็นผู้นำ ณ เวลาที่ 25 คะแนนคือ [0,1,1,0,0,1] และ 1 เป็นผู้นำ (ตามความเสมอกันไปสู่การโหวตล่าสุด) การดำเนินการนี้ดำเนินต่อไปอีก 3 ข้อความค้นหาในเวลา 15, 24 และสุดท้าย 8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างสองแผนที่ m และนับ

• ใน initializer ให้ทำดังนี้

• ตะกั่ว :=-1

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของอาร์เรย์ครั้ง

  • x :=ครั้ง[i]

  • เพิ่มมูลค่าการนับ[บุคคล[ผม]] ขึ้น 1

  • ถ้า count[lead] <=count[persons[i]] แล้ว lead :=persons[i] and m[x] :=lead มิฉะนั้น m[x] :=lead

• วิธีการ q() จะเป็นเช่นไร

  • ลดขอบเขตบนของ t เป็น m แล้วคืนค่าที่เกี่ยวข้อง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class TopVotedCandidate {
   public:
   map <int, int> m;
   map <int, int> count;
   TopVotedCandidate(vector<int>& persons, vector<int>& times) {
      int lead = -1;
      for(int i = 0; i < times.size(); i++){
         int x = times[i];
         count[persons[i]]++;
         if(count[lead] <= count[persons[i]]){
            lead = persons[i];
            m[x] = lead;
         }else{
            m[x] = lead;
         }
      }
   }
   int q(int t) {
      return ((--m.upper_bound(t)) -> second);
   }
};
main(){
   vector<int> v1 = {0,1,1,0,0,1,0}, v2 = {0,5,10,15,20,25,30};
   TopVotedCandidate ob(v1, v2);
   cout << (ob.q(3)) << endl;
   cout << (ob.q(12)) << endl;
   cout << (ob.q(25)) << endl;
   cout << (ob.q(15)) << endl;
   cout << (ob.q(24)) << endl;
   cout << (ob.q(8)) << endl;
}

อินพุต

Initialize the class using [0,1,1,0,0,1,0] and [0,5,10,15,20,25,30]. Call q()
method like below:
q(3)
q(12)
q(25)
q(15)
q(24)
q(8)

ผลลัพธ์

0
1
1
0
0
1