Advertisement
YEZAELP

SMMR-179: Policemen Catch Thieves

Apr 17th, 2021
173
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. string str;
  5.  
  6. int main(){
  7.  
  8.     int k;
  9.     scanf("%d", &k);
  10.  
  11.     cin >> str;
  12.     int l = str.size();
  13.     vector <int> T, P;
  14.     for(int i = 0; i < l; i ++){
  15.         if(str[i] == 'T') T.push_back(i);
  16.         else P.push_back(i);
  17.     }
  18.  
  19.     int cnt = 0;
  20.     int t = 0, p = 0;
  21.     int Ts = T.size(), Ps = P.size();
  22.     while(t < Ts and p < Ps){
  23.         while(abs(P[p] - T[t]) > k and p < Ps) {
  24.             if(P[p] < T[t]) p ++;
  25.             else t ++;
  26.         }
  27.         if(p >= Ps) break;
  28.         cnt ++;
  29.         p ++;
  30.         t ++;
  31.     }
  32.  
  33.     printf("%d", cnt);
  34.  
  35.     return 0;
  36. }
  37. /**
  38.  
  39. ex: k = 1
  40.     str = "TTPPTP"
  41. T = {0, 1, 4}
  42. P = {2, 3, 5}
  43. ถ้าตัวที่ไกลที่สุดจับได้ให้จับ จับไม่ได้ให้เลื่อนตำแหน่ง
  44. เพราะ ตำแหน่งของ P, T เรียงจาก น้อย(ใกล้)ไปมาก(ไกล)อยู่แล้ว
  45.  
  46. **/
Advertisement
RAW Paste Data Copied
Advertisement