Dada una array arr[] que consta de N enteros ( indexación basada en 1 ) y dos enteros M y S , la tarea es distribuir M objetos entre N personas, comenzando desde la posición S , de modo que la i -ésima persona obtenga como máximo arr [i] objetos cada vez.
Ejemplos:
Entrada: arr[] = {2, 3, 2, 1, 4}, M = 11, S = 2
Salida: 1, 3, 2, 1, 4
Explicación: La distribución de M (= 11) objetos a partir de S ª (= 2) persona es la siguiente:
- Para arr[2](= 3): Dar 3 objetos a la 2ª persona. Ahora, el número total de objetos se reduce a (11 – 3) = 8.
- Para arr[3] (= 2): Dar 2 objetos a la 3ª persona. Ahora, el número total de objetos se reduce a (8 – 2) = 6.
- Para arr[4] (= 1): Dar 1 objeto a la 4ª persona. Ahora, el número total de objetos se reduce a (6 – 1) = 5.
- Para arr[5] (= 4): Dar 4 objetos a la 5ª persona. Ahora, el número total de objetos se reduce a (5 – 4) = 1.
- Para arr[1] (= 1): Dar 1 objeto a la 1ª persona. Ahora, el número total de objetos reducido a (1 – 1) = 0.
Por lo tanto, la distribución de objetos es {1, 3, 2, 1, 4}.
Entrada: arr[] = {2, 3, 2, 1, 4}, M = 3, S = 4
Salida: 0 0 0 1 2
Enfoque: el problema dado se puede resolver recorriendo la array desde el índice inicial S y distribuyendo el máximo de objetos a cada elemento de la array. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array auxiliar, digamos distribution[] con todos los elementos como 0 para almacenar la distribución de M objetos .
- Inicialice dos variables, digamos ptr y rem como S y M respectivamente, para almacenar el índice inicial y los M objetos restantes .
- Iterar hasta que rem sea positivo y realizar los siguientes pasos:
- Si el valor de rem es al menos el elemento en el índice ptr , es decir, arr[ptr] , entonces incremente el valor de distribution[ptr] en arr[ptr] y disminuya el valor de rem en arr[ptr] .
- De lo contrario, incremente la distribución[ptr] por rem y actualice rem igual a 0 .
- Actualice ptr igual a (ptr + 1) % N para iterar la array dada arr[] de forma cíclica.
- Después de completar los pasos anteriores, imprima la distribución [] como la distribución resultante de objetos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find distribution of
// M objects among all array elements
void distribute(int N, int K,
int M, int arr[])
{
// Stores the distribution
// of M objects
int distribution[N] = { 0 };
// Stores the indices
// of distribution
int ptr = K - 1;
// Stores the remaining objects
int rem = M;
// Iterate until rem is positive
while (rem > 0) {
// If the number of remaining
// objects exceeds required
// the number of objects
if (rem >= arr[ptr]) {
// Increase the number of objects
// for the index ptr by arr[ptr]
distribution[ptr] += arr[ptr];
// Decrease remaining
// objects by arr[ptr]
rem -= arr[ptr];
}
else {
// Increase the number of objects
// for the index ptr by rem
distribution[ptr] += rem;
// Decrease remaining
// objects to 0
rem = 0;
}
// Increase ptr by 1
ptr = (ptr + 1) % N;
}
// Print the final distribution
for (int i = 0; i < N; i++) {
cout << distribution[i]
<< " ";
}
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 2, 1, 4 };
int M = 11, S = 2;
int N = sizeof(arr) / sizeof(arr[0]);
distribute(N, S, M, arr);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find distribution of
// M objects among all array elements
static void distribute(int N, int K, int M, int arr[])
{
// Stores the distribution
// of M objects
int distribution[] = new int[N];
// Stores the indices
// of distribution
int ptr = K - 1;
// Stores the remaining objects
int rem = M;
// Iterate until rem is positive
while (rem > 0) {
// If the number of remaining
// objects exceeds required
// the number of objects
if (rem >= arr[ptr]) {
// Increase the number of objects
// for the index ptr by arr[ptr]
distribution[ptr] += arr[ptr];
// Decrease remaining
// objects by arr[ptr]
rem -= arr[ptr];
}
else {
// Increase the number of objects
// for the index ptr by rem
distribution[ptr] += rem;
// Decrease remaining
// objects to 0
rem = 0;
}
// Increase ptr by 1
ptr = (ptr + 1) % N;
}
// Print the final distribution
for (int i = 0; i < N; i++) {
System.out.print(distribution[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 2, 1, 4 };
int M = 11, S = 2;
int N = arr.length;
distribute(N, S, M, arr);
}
}
// This code is contributed by Kingash.
Python3
# Python3 program for the above approach # Function to find distribution of # M objects among all array elements def distribute(N, K, M, arr): # Stores the distribution # of M objects distribution = [0] * N # Stores the indices # of distribution ptr = K - 1 # Stores the remaining objects rem = M # Iterate until rem is positive while (rem > 0): # If the number of remaining # objects exceeds required # the number of objects if (rem >= arr[ptr]): # Increase the number of objects # for the index ptr by arr[ptr] distribution[ptr] += arr[ptr] # Decrease remaining # objects by arr[ptr] rem -= arr[ptr] else: # Increase the number of objects # for the index ptr by rem distribution[ptr] += rem # Decrease remaining # objects to 0 rem = 0 # Increase ptr by 1 ptr = (ptr + 1) % N # Print the final distribution for i in range(N): print(distribution[i], end = " ") # Driver Code arr = [ 2, 3, 2, 1, 4 ] M = 11 S = 2 N = len(arr) distribute(N, S, M, arr) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to find distribution of
// M objects among all array elements
static void distribute(int N, int K,
int M, int []arr)
{
// Stores the distribution
// of M objects
int []distribution = new int[N];
// Stores the indices
// of distribution
int ptr = K - 1;
// Stores the remaining objects
int rem = M;
// Iterate until rem is positive
while (rem > 0)
{
// If the number of remaining
// objects exceeds required
// the number of objects
if (rem >= arr[ptr])
{
// Increase the number of objects
// for the index ptr by arr[ptr]
distribution[ptr] += arr[ptr];
// Decrease remaining
// objects by arr[ptr]
rem -= arr[ptr];
}
else
{
// Increase the number of objects
// for the index ptr by rem
distribution[ptr] += rem;
// Decrease remaining
// objects to 0
rem = 0;
}
// Increase ptr by 1
ptr = (ptr + 1) % N;
}
// Print the final distribution
for(int i = 0; i < N; i++)
{
Console.Write(distribution[i] + " ");
}
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 2, 3, 2, 1, 4 };
int M = 11, S = 2;
int N = arr.Length;
distribute(N, S, M, arr);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript program for the above approach
// Function to find distribution of
// M objects among all array elements
function distribute( N, K,
M, arr)
{
// Stores the distribution
// of M objects
let distribution = new Array(N)
for (let i = 0; i < N; i++) {
distribution[i]=0
}
// Stores the indices
// of distribution
let ptr = K - 1;
// Stores the remaining objects
let rem = M;
// Iterate until rem is positive
while (rem > 0) {
// If the number of remaining
// objects exceeds required
// the number of objects
if (rem >= arr[ptr]) {
// Increase the number of objects
// for the index ptr by arr[ptr]
distribution[ptr] += arr[ptr];
// Decrease remaining
// objects by arr[ptr]
rem -= arr[ptr];
}
else {
// Increase the number of objects
// for the index ptr by rem
distribution[ptr] += rem;
// Decrease remaining
// objects to 0
rem = 0;
}
// Increase ptr by 1
ptr = (ptr + 1) % N;
}
// Print the final distribution
for (let i = 0; i < N; i++) {
document.write(distribution[i]+" ")
}
}
// Driver Code
let arr = [ 2, 3, 2, 1, 4 ];
let M = 11, S = 2;
let N = arr.length
distribute(N, S, M, arr);
// This code is contributed by Hritik
</script>
Producción:
1 3 2 1 4
Complejidad temporal: O(M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por mamtagarg915 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA