Cảnh sát bắt trộm (Policemen catch thieves) trong C++

Trong bài toán này, chúng ta được cho mảng n phần tử. Mỗi phần tử là một cảnh sát (P) hoặc một trộm (T). Một trộm chỉ bị bắt bởi một cảnh sát. Ta phải tìm số lượng trộm tối đa mà cảnh sát có thể bắt nếu một cảnh sát có thể bắt trộm cách k đơn vị.

Ví dụ minh họa:

Đầu vào -

mảng = {T, P, P, P, T, T, T} K = 2.

Kết quả - 3

Giải thích - Mỗi cảnh sát bắt một trộm:

P tại chỉ số 1 bắt T tại chỉ số 0. 
P tại chỉ số 2 bắt T tại chỉ số 4. 
P tại chỉ số 3 bắt T tại chỉ số 5.

Điều này được phép vì cảnh sát có thể bắt trộm cách 2 đơn vị.

Để giải bài toán, dùng thuật toán tham lam (greedy). Có hai cách: bắt trộm gần nhất hoặc xa nhất. Nhưng cả hai đều không tối ưu trong mọi trường hợp.

Thuật toán cho kết quả tốt nhất:

Bắt đầu với chỉ số của cảnh sát đầu tiên và trộm đầu tiên. Nếu |index(P1) - index(T1)| ≤ k, trộm bị bắt, kiểm tra cặp cảnh sát-trộm tiếp theo. Ngược lại, tăng min(p,t) và kiểm tra chỉ số tiếp theo. Lặp cho đến khi hết cảnh sát hoặc trộm, in số trộm bị bắt.

Chương trình minh họa

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

int policeThief(char arr[], int n, int k) { 
    int caught = 0; 
    vector<int> thieves; 
    vector<int> policemen; 
    for (int i = 0; i < n; i++) { 
        if (arr[i] == 'P') 
            policemen.push_back(i); 
        else if (arr[i] == 'T') 
            thieves.push_back(i); 
    } 
    int thief = 0, police = 0; 
    while (thief < thieves.size() && police < policemen.size()) { 
        if (abs(thieves[thief] - policemen[police]) <= k) { 
            caught++; 
            thief++; 
            police++; 
        } else if (thieves[thief] < policemen[police]) 
            thief++; 
        else 
            police++; 
    } 
    return caught; 
} 

int main() { 
    int k, n; 
    char arr2[] = {'P', 'T', 'T', 'P', 'P', 'T', 'T', 'T', 'T', 'P'}; 
    k = 2; 
    n = sizeof(arr2) / sizeof(arr2[0]); 
    cout << "Số trộm tối đa bị bắt bởi cảnh sát là: " << policeThief(arr2, n, k); 
    return 0; 
}

Kết quả

Số trộm tối đa bị bắt bởi cảnh sát là: 4