โปรแกรม C++ นับขั้นต่ำ อีกกี่นาทีไม่มีนักศึกษาโกรธใหม่

สมมติว่าเรามีสตริง S ที่มีความยาว n โดยมีอักขระเพียงสองประเภทคือ 'A' หรือ 'P' มีนักเรียน n คนติดต่อกัน นักเรียน ith จะโกรธถ้า S[i] ='A' ถ้าเป็น 'P' แสดงว่า S[i] อดทน นักเรียนขี้โมโหที่ดัชนี ฉันจะตีนักเรียนที่อดทนด้วยดัชนี i+1 ทุกนาที และสำหรับนักเรียนคนสุดท้าย แม้จะโกรธ เขาไม่สามารถตีใครได้เลย หลังจากตีนักเรียนที่ป่วย นักเรียนคนนั้นก็โกรธเช่นกัน เราต้องหานาทีขั้นต่ำหลังจากนั้นไม่มีนักเรียนใหม่โกรธ

ดังนั้นหากอินพุตเป็น S ="PPAPP" เอาต์พุตจะเป็น 2 เพราะหลังจากนาทีแรกสตริงจะเป็น "PPAAP" จากนั้นในนาทีที่สอง "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