ความยาวสูงสุดของห่วงโซ่คู่ใน C++

สมมุติว่าในโลกของ Dota2 มีสองฝ่าย - The Radiant และ Dire วุฒิสภา Dota2 ประกอบด้วยวุฒิสมาชิกที่มาจากสองฝ่าย ตอนนี้วุฒิสภาต้องการสร้างทางเลือกใหม่ในเกม Dota2 การลงคะแนนสำหรับการเปลี่ยนแปลงนี้อาจเป็นขั้นตอนแบบรอบ ในแต่ละรอบ สมาชิกวุฒิสภาแต่ละคนสามารถใช้สิทธิได้หนึ่งสิทธิ -

• แบนสิทธิของสมาชิกวุฒิสภาคนหนึ่ง − สมาชิกวุฒิสภาสามารถทำให้สมาชิกวุฒิสภาอีกคนสูญเสียสิทธิ์ทั้งหมดของเขาในระหว่างนี้และทุกๆ รอบในรอบต่อๆ ไป

• ประกาศชัยชนะ − หากวุฒิสมาชิกรายนี้พบว่าสมาชิกวุฒิสภาที่ยังคงมีสิทธิลงคะแนนเสียงล้วนมาจากพรรคที่เท่าเทียมกัน เขาสามารถประกาศชัยชนะและเลือกเกี่ยวกับการเปลี่ยนแปลงในเกมได้

ระบุสตริงที่แสดงถึงพรรคของสมาชิกวุฒิสภาแต่ละคน ตัวละคร 'R' และ 'D' หมายถึงปาร์ตี้ Radiant และปาร์ตี้ Dire ตามลำดับ แล้วถ้ามีวุฒิสมาชิก n คน ขนาดของสตริงที่กำหนดจะเป็น n

ขั้นตอนตามรอบเริ่มตั้งแต่สมาชิกวุฒิสภาหลักไปจนถึงสมาชิกวุฒิสภาคนสุดท้ายภายในลำดับที่กำหนด ขั้นตอนนี้จะคงอยู่จนถึงจุดสูงสุดของการลงคะแนน สมาชิกวุฒิสภาทุกคนที่สูญเสียสิทธิ์จะถูกข้ามไปในระหว่างกระบวนการ

สมมติว่าวุฒิสมาชิกทุกคนมีเหตุผลเพียงพอและสามารถเล่นกลยุทธ์ที่ง่ายที่สุดสำหรับปาร์ตี้ของเขาเองได้ คุณต้องการคาดเดาว่าฝ่ายใดจะประกาศชัยชนะในที่สุดและทำการเปลี่ยนแปลงในเกม Dota2 ผลลัพธ์ควรเป็น Radiant หรือ Dire

ดังนั้นหากอินพุตเป็นเหมือน “RDD” ก็จะเป็น Dire เนื่องจากสมาชิกวุฒิสภาคนแรกมาจาก Radiant และเขาสามารถแบนสิทธิ์ของสมาชิกวุฒิสภาคนต่อไปในรอบที่ 1 ได้ และวุฒิสมาชิกคนที่สองก็ไม่สามารถใช้สิทธิได้อีกต่อไปเนื่องจากสิทธิ์ของเขาถูกแบน หลังจากนั้นสมาชิกวุฒิสภาคนที่สามมาจาก Dire และเขาสามารถแบนสิทธิ์ของสมาชิกวุฒิสภาคนแรกในรอบที่ 1 ได้ ตอนนี้ในรอบที่ 2 วุฒิสมาชิกคนที่สามสามารถประกาศชัยชนะได้เนื่องจากเขาเป็นคนเดียวในวุฒิสภาที่สามารถลงคะแนนเสียงได้

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

• สร้างคิว q1, q2, n :=ขนาดของสตริง สำหรับการแทรก R ทั้งหมดลงใน q1 และสำหรับ D ทั้งหมด ให้แทรกลงใน q2

• ขณะที่คิวทั้งสองไม่ว่าง

  • ถ้าองค์ประกอบด้านหน้าของ q1 <องค์ประกอบด้านหน้าของ q2 แล้ว

    • แทรก n ลงใน q1 ลบออกจาก q2 และ q1

  • มิฉะนั้นให้ใส่ n ลงใน q2 ให้ลบออกจาก q2 และ q1

  • เพิ่ม n โดย 1

• ถ้าคิวว่าง ให้คืน Dire มิฉะนั้น ให้คืน Radiant

ตัวอย่าง(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string predictPartyVictory(string s) {
      queue <int> q1, q2;
      int n = s.size();
      for(int i = 0; i < s.size(); i++){
         if(s[i] == 'R'){
            q1.push(i);
         } else {
            q2.push(i);
         }
      }
      while(q1.size() && q2.size()){
         if(q1.front() < q2.front()){
            q1.push(n);
            q2.pop();
            q1.pop();
         } else {
            q2.push(n);
            q2.pop();
            q1.pop();
         }
         n++;
      }
      return q1.empty()? "Dire" : "Radiant";
   }
};
main(){
   Solution ob;
   cout <<(ob.predictPartyVictory("RDD"));
}

อินพุต

"RDD"

ผลลัพธ์

Dire