ตำรวจจับโจรใน C++

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล −

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

ผลผลิต − 3

คำอธิบาย − ที่นี่ตำรวจแต่ละคนจะจับขโมย

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 แห่ง

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

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

เราจะเริ่มต้นด้วยดัชนีของตำรวจและโจรคนแรก ถ้า |ดัชนี(P1) - ดัชนี(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