Hay N lugares de pesca y 3 puertas. En cada puerta hay algunos pescadores esperando para llegar al lugar de pesca desocupado más cercano. (Número total de pescadores <=N)
Distancia entre lugares consecutivos = distancia entre la puerta y el lugar más cercano = 1 m
Solo se puede abrir 1 puerta a la vez y todos los pescadores de esa puerta deben ocupar los lugares antes de que se abra la siguiente puerta.
La distancia se calcula como la puerta al lugar más cercano + el lugar más cercano al lugar vacante más cercano.
Encuentre la suma total de las distancias mínimas que deben caminar todos los pescadores.
Entradas a tomar:
Número de lugares de pesca
Posición de las puertas
Número de pescadores en cada puerta
Sigue este ejemplo:
Número total de lugares de pesca = 10
5 pescadores en la puerta 1 ubicada en la posición 4,
2 pescadores en la puerta 2 ubicada en la posición 6,
2 pescadores en la puerta 3 ubicada en la posición 10,
si las puertas se abren en orden G1->G2->G3
El arreglo será:
La distancia se calcula como la puerta al lugar más cercano + el lugar más cercano al lugar vacante más cercano.
Después de abrir la puerta G1, los pescadores se colocan en los puntos marcados con 1.
Distancia = 11 m Después de
abrir la puerta G2, los pescadores se colocan en los puntos marcados con 2.
Distancia = 5 m
Después de abrir la puerta G3, los pescadores se colocan en los puntos marcados con 3
Distancia = 3m Distancia total en este orden :
11 + 5 + 3 = 19
Si las puertas se abren en orden G2->G1->G3
Caso 1 : el último pescador de la puerta 2 se coloca en la posición 7
, la disposición final será:
Después de abrir la puerta G2, los pescadores se colocan en los puntos marcados con 2.
Distancia = 3 m
Después de abrir la puerta G1, los pescadores se colocan en los puntos marcados con 1.
Distancia = 12 m
Después de abrir la puerta G3, los pescadores se colocan en los puntos marcados con 3
Distancia = 3m Distancia total en este orden :
3+12+3 = 18
Caso 2 : el último pescador de la puerta 2 se coloca en la posición 5
, la disposición final será:
Después de abrir la puerta G2, los pescadores se colocan en los puntos marcados con 2.
Distancia = 3 m
Después de abrir la puerta G1, los pescadores se colocan en los puntos marcados con 1.
Distancia = 14 m
Después de abrir la puerta G3, los pescadores se colocan en los puntos marcados con 3
Distancia = 3m Distancia total en este orden :
3+14+3 = 20
Otros casos son redundantes
por lo que la distancia mínima es 18
Solución:
Genere todas las combinaciones y asigne pescadores en todas las combinaciones de puertas para calcular la distancia mínima a pie.
La generación de combinaciones se puede hacer tanto de forma recursiva como iterativa. Ahora, para eliminar permutaciones innecesarias, podemos concluir que, para distancias mínimas a pie, los pescadores de una puerta en particular deben permanecer juntos, es decir, deben ocupar puntos de pesca consecutivos. Así podemos visualizar el problema como 3 bloques (grupo de pescadores) deslizándose por todo el rango de pesca. El mínimo de los cuales es la respuesta.
C++
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#define MAX 3
int fishspot[100]; // fishing spots
int gate[MAX]; // position of gates
int fishermen[MAX]; // no of fishermen at each gate
int N; // total no of fishing spots
int visited[MAX]; // occupied fishing spots
int Answer; // result
// To unmark spots occupied by fishermen of gate# index
class GFG
{
public :
void reset_fishspot(int index)
{
int i;
for (i = 1; i <= N; i++)
if (fishspot[i] == index + 1)
fishspot[i] = 0;
}
// Calculate minimum distance while
// allotting spots to fishermen of gate# index.
// Returns number of positions possible
// with minimum distance.
// pos1, pos2 is used to return positions
int calculate_distance(int index, int*pos1,
int *pos2, int *score)
{
int i, sum = 0, left_min = 999999,
right_min = 999999,
left, right, npos = 0;
*pos1 = *pos2 = *score = 0;
left = right = gate[index];
// Allot spots to all fishermen except
// last based on minimum distance
for (i = 1; i < fishermen[index]; i++)
{
if (fishspot[gate[index]] == 0)
{
sum++;
fishspot[gate[index]] = index + 1;
}
else
{
left_min = right_min = 999999;
while ((left > 0) && (fishspot[left] > 0))
left--;
while ((right <= N) &&
(fishspot[right] > 0))
right++;
if ((left > 0) && (fishspot[left] == 0))
left_min = gate[index] - left + 1;
if ((right <= N) && (fishspot[right] == 0))
right_min = right - gate[index] + 1;
if (right_min == left_min)
{
// Place 2 fishermen, if available
if ((fishermen[index] - i - 1) > 1)
{
fishspot[left] = fishspot[right] = index + 1;
sum += (2 * left_min);
i++;
// If all fishermen are alloted spots
if (i == fishermen[index])
{
npos = 1;
*score = sum;
return npos;
}
}
else
{
sum += left_min;
fishspot[left] = index + 1;
}
}
else if (left_min < right_min)
{
sum += left_min;
fishspot[left] = index + 1;
}
else if (right_min < left_min)
{
sum += right_min;
fishspot[right] = index + 1;
}
}
}
left_min = right_min = 99999;
// Allot spot to last fishermen
while ((left > 0) && (fishspot[left] > 0))
left--;
if ((left > 0) && (fishspot[left] == 0))
left_min = gate[index] - left + 1;
while ((right <= N) && (fishspot[right] > 0))
right++;
if ((right <= N) && (fishspot[right] == 0))
right_min = right - gate[index] + 1;
if ((sum + left_min) == (sum + right_min))
{
npos = 2;
*pos1 = left;
*pos2 = right;
*score = sum + left_min;
}
else if ((sum + left_min) >
(sum + right_min))
{
npos = 1;
*score = sum + right_min;
fishspot[right] = index + 1;
}
else if ((sum + left_min) <
(sum + right_min))
{
npos = 1;
*score = sum + left_min;
fishspot[left] = index + 1;
}
return npos;
}
// Solve is used to select next gate
// and generate all combinations.
void solve(int index, int sum, int count)
{
int npos, pos1, pos2, score, i;
visited[index] = 1;
if (sum > Answer)
return;
npos = calculate_distance(index, &pos1,
&pos2, &score);
sum += score;
if (count == MAX)
{
if (Answer > sum)
Answer = sum;
return;
}
if (npos == 1)
{
for (i = 0; i < MAX; i++)
{
if (visited[i] == 0)
{
solve(i, sum, count + 1);
visited[i] = 0;
reset_fishspot(i);
}
}
}
else if (npos == 2)
{
fishspot[pos1] = index + 1;
for (i = 0; i < MAX; i++)
{
if (visited[i] == 0)
{
solve(i, sum, count + 1);
visited[i] = 0;
reset_fishspot(i);
}
}
fishspot[pos1] = 0;
fishspot[pos2] = index + 1;
for (i = 0; i < MAX; i++)
{
if (visited[i] == 0)
{
solve(i, sum, count + 1);
visited[i] = 0;
reset_fishspot(i);
}
}
fishspot[pos2] = 0;
}
}
};
// Driver Code
int main()
{
GFG g;
int i;
/*scanf("%d", &N); // for input
for (i = 0; i < MAX; i++)
{
scanf("%d %d", &gate[i], &fishermen[i]);
visited[i] = 0;
}*/
N = 10; // total no of fishing spots
// position of gates(1-based indexing)
gate[0] = 4;
gate[1] = 6;
gate[2] = 10;
//no of fishermen at each gate
fishermen[0] = 5; //gate1
fishermen[1] = 2; //gate 2
fishermen[2] = 2; //gate 3
for (i = 1; i <= N; i++)
fishspot[i] = 0;
Answer = 999999;
for (i = 0; i < MAX; i++)
{
g.solve(i, 0, 1);
visited[i] = 0;
g.reset_fishspot(i);
}
cout << Answer << endl;
return 0;
}
// This code is contributed by SoM15242
C
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 3
int fishspot[100]; // fishing spots
int gate[MAX]; // position of gates
int fishermen[MAX]; // no of fishermen at each gate
int N; // total no of fishing spots
int visited[MAX]; // occupied fishing spots
int Answer; // result
//To unmark spots occupied by fishermen of gate# index
void reset_fishspot(int index)
{
int i;
for (i = 1; i <= N; i++)
if (fishspot[i] == index + 1)
fishspot[i] = 0;
}
// Calculate minimum distance while allotting spots to
// fishermen of gate# index.
// Returns number of positions possible with minimum distance.
// pos1, pos2 is used to return positions
int calculate_distance(int index, int*pos1, int *pos2, int *score)
{
int i, sum = 0, left_min = 999999, right_min = 999999,
left, right, npos = 0;
*pos1 = *pos2 = *score = 0;
left = right = gate[index];
// Allot spots to all fishermen except last based on
// minimum distance
for (i = 1; i < fishermen[index]; i++)
{
if (fishspot[gate[index]] == 0)
{
sum++;
fishspot[gate[index]] = index + 1;
}
else
{
left_min = right_min = 999999;
while ((left > 0) && (fishspot[left] > 0))
left--;
while ((right <= N) && (fishspot[right] > 0))
right++;
if ((left > 0) && (fishspot[left] == 0))
left_min = gate[index] - left + 1;
if ((right <= N) && (fishspot[right] == 0))
right_min = right - gate[index] + 1;
if (right_min == left_min)
{
// Place 2 fishermen, if available
if ((fishermen[index] - i - 1) > 1)
{
fishspot[left] = fishspot[right] = index + 1;
sum += (2 * left_min);
i++;
// If all fishermen are alloted spots
if (i == fishermen[index])
{
npos = 1;
*score = sum;
return npos;
}
}
else
{
sum += left_min;
fishspot[left] = index + 1;
}
}
else if (left_min < right_min)
{
sum += left_min;
fishspot[left] = index + 1;
}
else if (right_min < left_min)
{
sum += right_min;
fishspot[right] = index + 1;
}
}
}
left_min = right_min = 99999;
// Allot spot to last fishermen
while ((left > 0) && (fishspot[left] > 0))
left--;
if ((left > 0) && (fishspot[left] == 0))
left_min = gate[index] - left + 1;
while ((right <= N) && (fishspot[right] > 0))
right++;
if ((right <= N) && (fishspot[right] == 0))
right_min = right - gate[index] + 1;
if ((sum + left_min) == (sum + right_min))
{
npos = 2;
*pos1 = left;
*pos2 = right;
*score = sum + left_min;
}
else if ((sum + left_min) > (sum + right_min))
{
npos = 1;
*score = sum + right_min;
fishspot[right] = index + 1;
}
else if ((sum + left_min) < (sum + right_min))
{
npos = 1;
*score = sum + left_min;
fishspot[left] = index + 1;
}
return npos;
}
// Solve is used to select next gate and generate all combinations.
void solve(int index, int sum, int count)
{
int npos, pos1, pos2, score, i;
visited[index] = 1;
if (sum > Answer)
return;
npos = calculate_distance(index, &pos1, &pos2, &score);
sum += score;
if (count == MAX)
{
if (Answer > sum)
Answer = sum;
return;
}
if (npos == 1)
{
for (i = 0; i < MAX; i++)
{
if (visited[i] == 0)
{
solve(i, sum, count + 1);
visited[i] = 0;
reset_fishspot(i);
}
}
}
else if (npos == 2)
{
fishspot[pos1] = index + 1;
for (i = 0; i < MAX; i++)
{
if (visited[i] == 0)
{
solve(i, sum, count + 1);
visited[i] = 0;
reset_fishspot(i);
}
}
fishspot[pos1] = 0;
fishspot[pos2] = index + 1;
for (i = 0; i < MAX; i++)
{
if (visited[i] == 0)
{
solve(i, sum, count + 1);
visited[i] = 0;
reset_fishspot(i);
}
}
fishspot[pos2] = 0;
}
}
int main()// driver function
{
int i;
/*scanf("%d", &N); // for input
for (i = 0; i < MAX; i++)
{
scanf("%d %d", &gate[i], &fishermen[i]);
visited[i] = 0;
}*/
N=10; // total no of fishing spots
//position of gates(1-based indexing)
gate[0]=4;
gate[1]=6;
gate[2]=10;
//no of fishermen at each gate
fishermen[0]=5; //gate1
fishermen[1]=2; //gate 2
fishermen[2]=2; //gate 3
for (i = 1; i <= N; i++)
fishspot[i] = 0;
Answer = 999999;
for (i = 0; i < MAX; i++)
{
solve(i, 0, 1);
visited[i] = 0;
reset_fishspot(i);
}
printf("%d\n", Answer);
return 0;
}
Producción:
18
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