https://www.geeksforgeeks.org/policemen-catch-thieves/
Given an array of size n that has the following specifications:

  1. Each element in the array contains either a policeman or a thief.
  2. Each policeman can catch only one thief.
  3. A policeman cannot catch a thief who is more than K units away from the policeman.

We need to find the maximum number of thieves that can be caught.

Examples:
Input : arr[] = {‘P’, ‘T’, ‘T’, ‘P’, ‘T’},
k = 1.
Output : 2.
Here maximum 2 thieves can be caught, first
policeman catches first thief and second police-
man can catch either second or third thief.
Input : arr[] = {‘T’, ‘T’, ‘P’, ‘P’, ‘T’, ‘P’},
k = 2.
Output : 3.
Input : arr[] = {‘P’, ‘T’, ‘P’, ‘T’, ‘T’, ‘P’},
k = 3.
Output : 3.

focusing on just the allotment works
1) Get the lowest index of policeman p and thief t. Make an allotment
if |p-t| <= k and increment to the next p and t found.
2) Otherwise increment min(p, t) to the next p or t found.
3) Repeat above two steps until next p and t are found.
4) Return the number of allotments made

分析：考虑 P1 P2 , P1 在 P2 之前，如果 P1 与 一个 T 配对。
1）如果 T 在 P2 左侧区域 ，两种结果：
P2 左侧无 T 可选，此 T 更适合 P1 （即使选择 P2 对结果不造成影响）；P2 有 T 可选 ，P1 对 P2 不造成影响；
2）如果 T 在 P2 右侧，造成 P2 无 T 可选， 则选 P1 or P2 等同；若 P2 可选 则不影响； 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Returns maximum number of thieves that can 
// be caught. 
int policeThief(char arr[], int n, int k) 
{ 
    int res = 0; 
    vector<int> thi; 
    vector<int> pol; 
  
    // store indices in the vector 
    for (int i = 0; i < n; i++) { 
        if (arr[i] == 'P') 
            pol.push_back(i); 
        else if (arr[i] == 'T') 
            thi.push_back(i); 
    }    
  
    // track lowest current indices of 
    // thief: thi[l], police: pol[r] 
    int l = 0, r = 0; 
    while (l < thi.size() && r < pol.size()) { 
  
        // can be caught 
        if (abs(thi[l] - pol[r]) <= k) { 
            res++; 
            l++; 
            r++; 
        } 
  
        // increment the minimum index 
        else if (thi[l] < pol[r]) 
            l++; 
        else
            r++; 
    } 
  
    return res; 
}