新しい怒っている学生がいなくなってから最低何分かを数えるC++プログラム

長さnの文字列Sがあり、「A」または「P」の2種類の文字しかないとします。 n人の生徒が並んでいます。S[i]='A'の場合、i番目の生徒は怒っています。'P'の場合、S[i]は忍耐強いと言います。インデックスiで怒っている学生は、毎分インデックスi + 1で患者の学生を攻撃します。最後の学生は、怒っていても、誰も攻撃できません。忍耐強い学生を殴った後、その学生も怒ります。その後、新入生が怒らないようにするための最小時間を見つける必要があります。

したがって、入力がS ="PPAPP"の場合、出力は2になります。これは、最初の1分後に文字列が「PPAAP」になり、2分後に「PPAAA」になり、新しい学生が再び怒ることがないためです。

ステップ

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

n := size of S
ans := 0, cnt = 0
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
   if S[i] is same as 'P', then:
      (increase cnt by 1)
   Otherwise
      ans := maximum of ans and cnt
      cnt := 0
return ans

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

int solve(string S) {
   int n = S.size();
   int ans = 0, cnt = 0;
   for (int i = n - 1; i >= 0; i--) {
      if (S[i] == 'P') {
         cnt++;
      } else {
         ans = max(ans, cnt);
         cnt = 0;
      }
   }
   return ans;
}
int main() {
   string S = "PPAPP";
   cout << solve(S) << endl;
}

入力

PPAPP

出力

2