Dada una array de tamaño n que tiene las siguientes especificaciones:
- Cada elemento de la array contiene un policía o un ladrón.
- Cada policía puede atrapar a un solo ladrón.
- Un policía no puede atrapar a un ladrón que está a más de K unidades del policía.
Necesitamos encontrar el número máximo de ladrones que se pueden atrapar.
Ejemplos:
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.
Un enfoque de fuerza bruta sería verificar todos los conjuntos factibles de combinaciones de policía y ladrón y devolver el conjunto de tamaño máximo entre ellos. Su complejidad temporal es exponencial y puede optimizarse si observamos una propiedad importante.
Una solución eficiente es utilizar un algoritmo codicioso. Pero qué propiedad codiciosa
usar puede ser complicado. Podemos intentar usar: «Por cada policía de la izquierda, atrape al ladrón más cercano posible». Esto funciona en el ejemplo tres dado anteriormente, pero falla en el ejemplo dos, ya que genera 2, lo cual es incorrecto.
También podemos intentar: “Por cada policía de la izquierda atrapar al ladrón más lejano posible”. Esto funciona, por ejemplo, en los dos ejemplos anteriores, pero falla en el ejemplo tres, ya que genera 2, lo cual es incorrecto. Se puede aplicar un argumento simétrico para mostrar que el recorrido de estos desde el lado derecho de la array también falla. Podemos observar que pensar independientemente del
policía y centrarse solo en la asignación funciona:
1. Obtener el índice más bajo de policía p y ladrón t. Hacer una asignación
si |pt| <= k y se incrementa a la siguiente p y t encontrada.
2. De lo contrario, incremente min(p, t) al siguiente p o t encontrado.
3. Repita los dos pasos anteriores hasta encontrar la siguiente p y t.
4. Devolver el número de adjudicaciones realizadas.
A continuación se muestra la implementación del algoritmo anterior. Utiliza vectores para
almacene los índices de policía y ladrón en la array y los procese.
C++
// C++ program to find maximum number of thieves
// caught
#include<bits/stdc++.h>
using namespace std;
// 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++;
// increment the minimum index
else if (thi[l] < pol[r])
l++;
else
r++;
}
return res;
}
int main()
{
int k, n;
char arr1[] = { 'P', 'T', 'T', 'P', 'T' };
k = 2;
n = sizeof(arr1) / sizeof(arr1[0]);
cout << "Maximum thieves caught: " << policeThief(arr1, n, k) << endl;
char arr2[] = { 'T', 'T', 'P', 'P', 'T', 'P' };
k = 2;
n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Maximum thieves caught: " << policeThief(arr2, n, k) << endl;
char arr3[] = { 'P', 'T', 'P', 'T', 'T', 'P' };
k = 3;
n = sizeof(arr3) / sizeof(arr3[0]);
cout << "Maximum thieves caught: " << policeThief(arr3, n, k) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find maximum number of
// thieves caught
import java.util.*;
import java.io.*;
class GFG
{
// Returns maximum number of thieves
// that can be caught.
static int policeThief(char arr[], int n, int k)
{
int res = 0;
ArrayList<Integer> thi = new ArrayList<Integer>();
ArrayList<Integer> pol = new ArrayList<Integer>();
// store indices in the ArrayList
for (int i = 0; i < n; i++) {
if (arr[i] == 'P')
pol.add(i);
else if (arr[i] == 'T')
thi.add(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 (Math.abs(thi.get(l++) - pol.get(r++)) <= k)
res++;
// increment the minimum index
else if (thi.get(l) < pol.get(r))
l++;
else
r++;
}
return res;
}
public static void main(String args[])
{
int k, n;
char arr1[] = new char[] { 'P', 'T', 'T', 'P', 'T' };
k = 2;
n = arr1.length;
System.out.println("Maximum thieves caught: " + policeThief(arr1, n, k));
char arr2[] = new char[] { 'T', 'T', 'P', 'P', 'T', 'P' };
k = 2;
n = arr2.length;
System.out.println("Maximum thieves caught: " + policeThief(arr2, n, k));
char arr3[] = new char[] { 'P', 'T', 'P', 'T', 'T', 'P' };
k = 3;
n = arr3.length;
System.out.println("Maximum thieves caught: " + policeThief(arr3, n, k));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
C#
// C# program to find maximum number of
// thieves caught
using System;
using System.Collections.Generic;
public class GFG{
// Returns maximum number of thieves
// that can be caught.
static int policeThief(char[] arr, int n, int k)
{
int res = 0;
List<int> thi = new List<int>();
List<int> pol = new List<int>();
// store indices in the ArrayList
for (int i = 0; i < n; i++) {
if (arr[i] == 'P')
pol.Add(i);
else if (arr[i] == 'T')
thi.Add(i);
}
// track lowest current indices of
// thief: thi[l], police: pol[r]
int l = 0, r = 0;
while (l < thi.Count && r < pol.Count) {
// can be caught
if (Math.Abs(thi[l++] - pol[r++]) <= k){
res++;
}else{
if (thi[l] < pol[r]){
l++;
}else{
r++;
}
}
}
return res;
}
static public void Main (){
int k, n;
char[] arr1 = { 'P', 'T', 'T', 'P', 'T' };
k = 2;
n = arr1.Length;
Console.Write("Maximum thieves caught: " + policeThief(arr1, n, k)+"\n");
char[] arr2 = { 'T', 'T', 'P', 'P', 'T', 'P' };
k = 2;
n = arr2.Length;
Console.Write("Maximum thieves caught: " + policeThief(arr2, n, k)+"\n");
char[] arr3 = { 'P', 'T', 'P', 'T', 'T', 'P' };
k = 3;
n = arr3.Length;
Console.Write("Maximum thieves caught: " + policeThief(arr3, n, k)+"\n");
}
}
//This code is contributed by shruti456rawal
Python3
# Python3 program to find maximum
# number of thieves caught
# Returns maximum number of thieves
# that can be caught.
def policeThief(arr, n, k):
i = 0
l = 0
r = 0
res = 0
thi = []
pol = []
# store indices in list
while i < n:
if arr[i] == 'P':
pol.append(i)
elif arr[i] == 'T':
thi.append(i)
i += 1
# track lowest current indices of
# thief: thi[l], police: pol[r]
while l < len(thi) and r < len(pol):
# can be caught
if (abs( thi[l] - pol[r] ) <= k):
res += 1
l += 1
r += 1
# increment the minimum index
elif thi[l] < pol[r]:
l += 1
else:
r += 1
return res
# Driver program
if __name__=='__main__':
arr1 = ['P', 'T', 'T', 'P', 'T']
k = 2
n = len(arr1)
print(("Maximum thieves caught: {}".
format(policeThief(arr1, n, k))))
arr2 = ['T', 'T', 'P', 'P', 'T', 'P']
k = 2
n = len(arr2)
print(("Maximum thieves caught: {}".
format(policeThief(arr2, n, k))))
arr3 = ['P', 'T', 'P', 'T', 'T', 'P']
k = 3
n = len(arr3)
print(("Maximum thieves caught: {}".
format(policeThief(arr3, n, k))))
# This code is contributed by `jahid_nadim`
Javascript
<script>
// JavaScript program to find maximum
// number of thieves caught
// Returns maximum number of thieves
// that can be caught.
function policeThief(arr, n, k){
let i = 0
let l = 0
let r = 0
let res = 0
let thi = []
let pol = []
// store indices in list
while(i < n){
if(arr[i] == 'P')
pol.push(i)
else if(arr[i] == 'T')
thi.push(i)
i += 1
}
// track lowest current indices of
// thief: thi[l], police: pol[r]
while(l < thi.length && r < pol.length){
// can be caught
if (Math.abs( thi[l] - pol[r] ) <= k){
res += 1
l += 1
r += 1
}
// increment the minimum index
else if(thi[l] < pol[r])
l += 1
else
r += 1
}
return res
}
// Driver program
let arr1 = ['P', 'T', 'T', 'P', 'T']
let k = 2
let n = arr1.length
document.write("Maximum thieves caught: ",policeThief(arr1, n, k),"</br>")
let arr2 = ['T', 'T', 'P', 'P', 'T', 'P']
k = 2
n = arr2.length
document.write("Maximum thieves caught: ",policeThief(arr2, n, k),"</br>")
let arr3 = ['P', 'T', 'P', 'T', 'T', 'P']
k = 3
n = arr3.length
document.write("Maximum thieves caught: ",policeThief(arr3, n, k),"</br>")
// This code is contributed by shinjanpatra
</script>
Producción
Maximum thieves caught: 2 Maximum thieves caught: 3 Maximum thieves caught: 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
El siguiente método funciona en la complejidad del espacio O(1)
Acercarse:
Este enfoque sigue los siguientes pasos:
- Primero encuentre al policía y al ladrón más a la izquierda y almacene los índices. Puede haber dos casos:
- CASO 1: Si la distancia entre el policía y el ladrón <= k (dada), el ladrón puede ser atrapado, por lo que incrementa el contador de res
- CASO 2: Si la distancia entre el policía y el ladrón >= k, el ladrón actual no puede ser atrapado por el policía actual
- Para el CASO 2 , si la policía está detrás del ladrón , necesitamos encontrar al próximo policía y verificar si puede atrapar al ladrón actual.
- si el ladrón está detrás de la policía, debemos encontrar al próximo ladrón y verificar si la policía actual puede atrapar al ladrón
- Repita el proceso hasta que encontremos el siguiente par de policías y ladrones, e incremente el contador de resultados si se cumplen las condiciones, es decir, CASO 1.
Algoritmo:
1. Inicialice los índices más bajos actuales de policía en pol y ladrón en esta variable como -1.
2 Encuentra el índice más bajo de policía y ladrón.
3 Si el índice más bajo de policía o ladrón sigue siendo -1, devuelve 0.
4 Si |pol – thi| <=k luego haga una asignación y encuentre al próximo policía y ladrón.
5 De lo contrario, incremente el min(pol , thi) hasta el siguiente policía o ladrón encontrado.
6 Repita los dos pasos anteriores hasta que podamos encontrar al siguiente policía y ladrón.
7 Devolver el número de adjudicaciones realizadas.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to find maximum number of thieves caught
#include <bits/stdc++.h>
using namespace std;
// Returns maximum number of thieves that can be caught.
int policeThief(char arr[], int n, int k)
{
// Initialize the current lowest indices of
// policeman in pol and thief in thi variable as -1
int pol = -1, thi = -1, res = 0;
// Find the lowest index of policemen
for (int i = 0; i < n; i++) {
if (arr[i] == 'P') {
pol = i;
break;
}
}
// Find the lowest index of thief
for (int i = 0; i < n; i++) {
if (arr[i] == 'T') {
thi = i;
break;
}
}
// If lowest index of either policemen or thief remain
// -1 then return 0
if (thi == -1 || pol == -1)
return 0;
while (pol < n && thi < n) {
// can be caught
if (abs(pol - thi) <= k) {
pol = pol + 1;
while (pol < n && arr[pol] != 'P')
pol = pol + 1;
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi = thi + 1;
res++;
}
// increment the current min(pol , thi) to
// the next policeman or thief found
else if (thi < pol) {
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi = thi + 1;
}
else {
pol = pol + 1;
while (pol < n && arr[pol] != 'P')
pol = pol + 1;
}
}
return res;
}
int main()
{
int k, n;
char arr1[] = { 'P', 'T', 'T', 'P', 'T' };
k = 2;
n = sizeof(arr1) / sizeof(arr1[0]);
cout << "Maximum thieves caught: " << policeThief(arr1, n, k) << endl;
char arr2[] = { 'T', 'T', 'P', 'P', 'T', 'P' };
k = 2;
n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Maximum thieves caught: " << policeThief(arr2, n, k) << endl;
char arr3[] = { 'P', 'T', 'P', 'T', 'T', 'P' };
k = 3;
n = sizeof(arr3) / sizeof(arr3[0]);
cout << "Maximum thieves caught: " << policeThief(arr3, n, k) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find maximum number of thieves
// caught
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
// Returns maximum number of thieves that can
// be caught.
int policeThief(char arr[], int n, int k)
{
// Initialize the current lowest indices of
// policeman in pol and thief in thi variable as -1
int pol = -1, thi = -1, res = 0;
// Find the lowest index of policemen
for (int i = 0; i < n; i++) {
if (arr[i] == 'P') {
pol = i;
break;
}
}
// Find the lowest index of thief
for (int i = 0; i < n; i++) {
if (arr[i] == 'T') {
thi = i;
break;
}
}
// If lowest index of either policemen or thief remain
// -1 then return 0
if (thi == -1 || pol == -1)
return 0;
while (pol < n && thi < n) {
// can be caught
if (abs(pol - thi) <= k) {
pol = pol + 1;
while (pol < n && arr[pol] != 'P')
pol = pol + 1;
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi = thi + 1;
res++;
}
// increment the current min(pol , thi) to
// the next policeman or thief found
else if (thi < pol) {
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi = thi + 1;
}
else {
pol = pol + 1;
while (pol < n && arr[pol] != 'P')
pol = pol + 1;
}
}
return res;
}
// Driver Code Starts.
int main()
{
int k, n;
char arr1[] = { 'P', 'T', 'T', 'P', 'T' };
k = 2;
n = sizeof(arr1) / sizeof(arr1[0]);
printf("Maximum thieves caught: %d\n", policeThief(arr1, n, k));
char arr2[] = { 'T', 'T', 'P', 'P', 'T', 'P' };
k = 2;
n = sizeof(arr2) / sizeof(arr2[0]);
printf("Maximum thieves caught: %d\n", policeThief(arr2, n, k));
char arr3[] = { 'P', 'T', 'P', 'T', 'T', 'P' };
k = 3;
n = sizeof(arr3) / sizeof(arr3[0]);
printf("Maximum thieves caught: %d\n", policeThief(arr3, n, k));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find maximum number of
// thieves caught
import java.io.*;
import java.util.*;
class GFG {
// Returns maximum number of thieves that can be caught.
static int policeThief(char arr[], int n, int k)
{
int pol = -1, thi = -1, res = 0;
// store the first index of police in pol
for (int i = 0; i < n; i++) {
if (arr[i] == 'P') {
pol = i;
break;
}
}
// store the first index of thief in thi
for (int i = 0; i < n; i++) {
if (arr[i] == 'T') {
thi = i;
break;
}
}
// return 0 if no police OR no thief found
if (thi == -1 || pol == -1)
return 0;
// loop to increase res iff distance between police
// and thief <= k
while (pol < n && thi < n) {
// thief can be caught
if (Math.abs(pol - thi) <= k) {
pol++;
// to find the index of next police for next
// iteration
while (pol < n && arr[pol] != 'P')
pol++;
// to find the index of next thief for next
// iteration
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi++;
// increment res, as the thief has been
// caugh
res++;
}
// thief cannot be caught as dist > k
else if (thi < pol) {
// as index of thief is behind police, we
// need to find the next thief and check if
// it can be caught by the current police
// (it will be checked in the next
// iteration) Hence, find the index of next
// thief
thi++;
while (thi < n && arr[thi] != 'T')
thi++;
}
else {
// as the index of police is behind the
// thief, it cannot catch the thief. Hence,
// we need the index of next police and
// check if it can catch the current thief
// (it will be checked in the next
// iteration)
pol++;
while (pol < n && arr[pol] != 'P')
pol++;
}
}
return res;
}
// Driver code starts
public static void main(String[] args)
{
char arr1[] = { 'P', 'T', 'T', 'P', 'T' };
int n = arr1.length;
int k = 2;
System.out.println("Maximum thieves caught: " + policeThief(arr1, n, k));
char arr2[] = { 'T', 'T', 'P', 'P', 'T', 'P' };
n = arr2.length;
k = 2;
System.out.println("Maximum thieves caught: " + policeThief(arr2, n, k));
char arr3[] = { 'P', 'T', 'P', 'T', 'T', 'P' };
n = arr3.length;
k = 3;
System.out.println("Maximum thieves caught: " + policeThief(arr3, n, k));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Javascript
<script>
// JavaScript program to find maximum number of thieves caught
// Returns maximum number of thieves that can be caught.
function policeThief(arr, n, k)
{
// Initialize the current lowest indices of
// policeman in pol and thief in thi variable as -1
let pol = -1, thi = -1, res = 0;
// Find the lowest index of policemen
for (let i = 0; i < n; i++) {
if (arr[i] == 'P') {
pol = i;
break;
}
}
// Find the lowest index of thief
for (let i = 0; i < n; i++) {
if (arr[i] == 'T') {
thi = i;
break;
}
}
// If lowest index of either policemen or thief remain
// -1 then return 0
if (thi == -1 || pol == -1)
return 0;
while (pol < n && thi < n)
{
// can be caught
if (Math.abs(pol - thi) <= k) {
pol = pol + 1;
while (pol < n && arr[pol] != 'P')
pol = pol + 1;
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi = thi + 1;
res++;
}
// increment the current min(pol , thi) to
// the next policeman or thief found
else if (thi < pol) {
thi = thi + 1;
while (thi < n && arr[thi] != 'T')
thi = thi + 1;
}
else {
pol = pol + 1;
while (pol < n && arr[pol] != 'P')
pol = pol + 1;
}
}
return res;
}
// driver code
let k, n;
let arr1 = [ 'P', 'T', 'T', 'P', 'T' ];
k = 2;
n = arr1.length;
document.write("Maximum thieves caught: ",policeThief(arr1, n, k),"</br>");
let arr2 = [ 'T', 'T', 'P', 'P', 'T', 'P' ];
k = 2;
n = arr2.length;
document.write("Maximum thieves caught: ",policeThief(arr2, n, k),"</br>");
let arr3 = [ 'P', 'T', 'P', 'T', 'T', 'P' ];
k = 3;
n = arr3.length;
document.write("Maximum thieves caught: ",policeThief(arr3, n, k),"</br>");
// This code is contributed by shinjanpatra
</script>
Python3
# Python program to find maximum number of thieves caught
# Returns maximum number of thieves that can be caught.
def policeThief(arr, n, k):
# Initialize the current lowest indices of
# policeman in pol and thief in thi variable as -1
pol,thi,res = -1,-1,0
# Find the lowest index of policemen
for i in range(n):
if (arr[i] == 'P'):
pol = i
break
# Find the lowest index of thief
for i in range(n):
if (arr[i] == 'T'):
thi = i
break
# If lowest index of either policemen or thief remain
# -1 then return 0
if (thi == -1 or pol == -1):
return 0
while (pol < n and thi < n):
# can be caught
if (abs(pol - thi) <= k):
pol = pol + 1
while (pol < n and arr[pol] != 'P'):
pol = pol + 1
thi = thi + 1
while (thi < n and arr[thi] != 'T'):
thi = thi + 1
res += 1
# increment the current min(pol , thi) to
# the next policeman or thief found
elif (thi < pol):
thi = thi + 1
while (thi < n and arr[thi] != 'T'):
thi = thi + 1
else:
pol = pol + 1
while (pol < n and arr[pol] != 'P'):
pol = pol + 1
return res
# driver code
arr1 = [ 'P', 'T', 'T', 'P', 'T' ];
k = 2;
n = len(arr1)
print("Maximum thieves caught: " + str(policeThief(arr1, n, k)))
arr2 = [ 'T', 'T', 'P', 'P', 'T', 'P' ];
k = 2;
n = len(arr2)
print("Maximum thieves caught: "+ str(policeThief(arr2, n, k)))
arr3 = [ 'P', 'T', 'P', 'T', 'T', 'P' ];
k = 3;
n = len(arr3)
print("Maximum thieves caught: "+ str(policeThief(arr3, n, k)))
# This code is contributed by shinjanpatra
Producción
Maximum thieves caught: 2 Maximum thieves caught: 3 Maximum thieves caught: 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Este artículo es una contribución de Satish Srinivas . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA