C++でのペアチェーンの最大長

Dota2の世界で、ラディアントとダイアの2つのパーティがあるとします。 Dota2上院議員は、2つの政党から来た上院議員で構成されています。今、上院はDota2ゲーム内でいくつかの変更を選択したいと考えています。この変更への投票は、ラウンドベースの手順である可能性があります。各ラウンドで、各上院議員は2つの権利のうちの1つを行使できます-

• 1人の上院議員の権利を禁止する-上院議員は、このラウンドとその後のラウンドで、別の上院議員にすべての権利を失う可能性があります。

• 勝利を発表する-この上院議員が、まだ投票権を持っている上院議員がすべて同等の政党から来ていることを発見した場合、彼は勝利を発表し、ゲーム内の変更について選択することができます。

各上院議員の所属するパーティーを表す文字列が与えられます。文字「R」と「D」は、それぞれラディアントパーティーとダイアパーティーを表しています。次に、上院議員がn人いる場合、指定された文字列の次元はnになります。

ラウンドベースの手順は、指定された順序内の最初の上院議員から最後の上院議員まで始まります。この手順は、投票のトップまで続きます。権利を失った上院議員は全員、手続き中にスキップされます。

すべての上院議員が十分に賢明であり、彼自身の党のために最も単純な戦略を演じることができると仮定すると、どの党が最終的に勝利を発表し、Dota2ゲーム内で変更を加えるかを予測したいと思います。出力はRadiantまたはDireである必要があります。

したがって、入力が「RDD」のようなものである場合、それはDireになります。これは、最初の上院議員がラディアント出身であり、ラウンド1で次の上院議員の権利を禁止できるためです。2番目の上院議員は、権利が禁止されたため、権利を行使できなくなりました。その後、3番目の上院議員はダイアから来て、ラウンド1で最初の上院議員の権利を禁止することができます。今ラウンド2では、3番目の上院議員は上院で投票できる唯一の男なので勝利を発表できます。

これを解決するには、次の手順に従います-

• キューq1、q2、n：=文字列のサイズを作成します。すべてのRに​​ついてはq1に挿入し、すべてのDについてはq2に挿入します。

• 両方のキューが空ではない間

  • q1のフロント要素

    • 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