Policemen Catch Thieves (ตำรวจจับขโมย) ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของ n องค์ประกอบ แต่ละองค์ประกอบของอาร์เรย์มี either ตำรวจหรือขโมย ขโมยหนึ่งคนสามารถถูกจับโดยตำรวจหนึ่งคน และเราต้องหาจำนวนขโมยสูงสุดที่สามารถจับได้โดยตำรวจ หากตำรวจสามารถจับขโมยได้ที่ห่าง k หน่วยจากเขา

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input -

array = {T, P, P, P, T, T, T} K = 2.

Output - 3

Explanation - ที่นี่ ตำรวจแต่ละคนจะจับขโมยหนึ่งคน

P at index 1 will catch T at index 0.
P at index 2 will catch T at index 4.
P at index 3 will catch T at index 5.

สิ่งนี้ได้รับอนุญาต เนื่องจากตำรวจสามารถจับขโมยที่อยู่ห่าง 2 หน่วยจากพวกเขา

เพื่อแก้ปัญหานี้ เราจะใช้ greedy algorithm มันสามารถทำงานได้สองวิธี คือจับขโมยทั้งหมดที่ใกล้ตำรวจที่สุด หรือจับขโมยที่ไกลที่สุดจากตำรวจ แต่ในทั้งสองกรณี โซลูชันที่เหมาะสมที่สุดไม่ได้ถูกพบ เนื่องจากทั้งสองล่าช้าในบางกรณีที่ตำรวจต้องจับขโมยที่ระยะห่างบางระยะจากเขา

ดังนั้น อัลกอริทึมต่อไปนี้คืออัลกอริทึมที่ให้ผลลัพธ์ที่มีความเป็นไปได้สูงสุด:

เราจะเริ่มต้นด้วยดัชนีของตำรวจคนแรกและขโมยคนแรก หาก |index(P1) - index(T1)| <= k ขโมยสามารถจับได้ และเราจะตรวจสอบคู่ตำรวจ-ขโมยถัดไป มิฉะนั้น เราจะเพิ่ม min(p,t) และตรวจสอบดัชนีถัดไปของตำรวจและขโมย การตรวจสอบนี้จะทำจนกว่าตำรวจและขโมยทั้งหมดจะถูกตรวจสอบ และในท้ายที่สุด จำนวนขโมยที่ถูกจับจะถูกพิมพ์

ตัวอย่าง

โปรแกรมแสดงการประกอบอัลกอริทึมของเรา:

#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 << "Maximum number of thieves that can be caught by police is :" << policeThief(arr2, n, k);
    return 0;
}

ผลลัพธ์

Maximum number of thieves that can be caught by police is :4