Dada una array , arr[] de tamaño N y un entero T. La tarea es encontrar para cada índice el número mínimo de índices que deben omitirse si la suma hasta el i-ésimo índice no debe exceder T.
Ejemplos:
Entrada: N = 7, T = 15, arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida: 0 0 0 0 0 2 3
Explicación: No es necesario omitir ningún índice para los primeros 5 índices: {1, 2, 3, 4, 5}, ya que su suma es 15 y <= T.
Para el sexto índice, se pueden omitir los índices 3 y 4, lo que hace que su suma = (1+2+3+6 ) = 12.
Para el séptimo, se pueden omitir los índices 3, 4 y 5, lo que hace que su suma = (1+2+3+7) = 13.Entrada: N =2, T = 100, arr[] = {100, 100}
Salida: 0 1
Enfoque: La idea es usar un mapa para almacenar los elementos visitados en orden creciente mientras se recorre. Siga los pasos a continuación para resolver el problema:
- Cree un mapa ordenado , M para llevar un recuento de los elementos antes del i-ésimo índice.
- Inicialice una suma variable como 0 para almacenar la suma del prefijo.
- Atraviesa la array , arr[] usando la variable i
- Almacene la diferencia de sum+arr[i] y T en una variable, d .
- Si el valor de d>0 , recorre el mapa desde el final y selecciona los índices con los elementos más grandes hasta que la suma sea menor que T. Almacene el número de elementos requeridos en una variable k .
- Agregue arr[i] a la suma e incremente A[i] en M en 1 .
- Imprime el valor de k .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ approach for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate minimum indices to be skipped
// so that sum till i remains smaller than T
void skipIndices(int N, int T, int arr[])
{
// Store the sum of all indices before i
int sum = 0;
// Store the elements that can be skipped
map<int, int> count;
// Traverse the array, A[]
for (int i = 0; i < N; i++) {
// Store the total sum of elements that
// needs to be skipped
int d = sum + arr[i] - T;
// Store the number of elements need
// to be removed
int k = 0;
if (d > 0) {
// Traverse from the back of map so
// as to take bigger elements first
for (auto u = count.rbegin(); u != count.rend();
u++) {
int j = u->first;
int x = j * count[j];
if (d <= x) {
k += (d + j - 1) / j;
break;
}
k += count[j];
d -= x;
}
}
// Update sum
sum += arr[i];
// Update map with the current element
count[arr[i]]++;
cout << k << " ";
}
}
// Driver code
int main()
{
// Given Input
int N = 7;
int T = 15;
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
// Function Call
skipIndices(N, T, arr);
return 0;
}
Java
import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;
// C++ approach for above approach
class GFG {
// Function to calculate minimum indices to be skipped
// so that sum till i remains smaller than T
public static void skipIndices(int N, int T, int arr[])
{
// Store the sum of all indices before i
int sum = 0;
// Store the elements that can be skipped
TreeMap<Integer, Integer> count = new TreeMap<Integer, Integer>();
// Traverse the array, A[]
for (int i = 0; i < N; i++) {
// Store the total sum of elements that
// needs to be skipped
int d = sum + arr[i] - T;
// Store the number of elements need
// to be removed
int k = 0;
if (d > 0) {
// Traverse from the back of map so
// as to take bigger elements first
for (Map.Entry<Integer, Integer> u : count.descendingMap().entrySet()) {
int j = u.getKey();
int x = j * count.get(j);
if (d <= x) {
k += (d + j - 1) / j;
break;
}
k += count.get(j);
d -= x;
}
}
// Update sum
sum += arr[i];
// Update map with the current element
if(count.containsKey(arr[i])){
count.put(arr[i], count.get(arr[i]) + 1);
}else{
count.put(arr[i], 1);
}
System.out.print(k + " ");
}
}
// Driver code
public static void main(String args[])
{
// Given Input
int N = 7;
int T = 15;
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
// Function Call
skipIndices(N, T, arr);
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python3 approach for above approach
# Function to calculate minimum indices to be skipped
# so that sum till i remains smaller than T
def skipIndices(N, T, arr):
# Store the sum of all indices before i
sum = 0
# Store the elements that can be skipped
count = {}
# Traverse the array, A[]
for i in range(N):
# Store the total sum of elements that
# needs to be skipped
d = sum + arr[i] - T
# Store the number of elements need
# to be removed
k = 0
if (d > 0):
# Traverse from the back of map so
# as to take bigger elements first
for u in list(count.keys())[::-1]:
j = u
x = j * count[j]
if (d <= x):
k += (d + j - 1) // j
break
k += count[j]
d -= x
# Update sum
sum += arr[i]
# Update map with the current element
count[arr[i]] = count.get(arr[i], 0) + 1
print(k, end = " ")
# Driver code
if __name__ == '__main__':
# Given Input
N = 7
T = 15
arr = [1, 2, 3, 4, 5, 6, 7]
# Function Call
skipIndices(N, T, arr)
# This code is contributed by mohit kumar 29.
Javascript
<script>
// Javascript approach for above approach
// Function to calculate minimum indices
// to be skipped so that sum till i
// remains smaller than T
function skipIndices(N, T, arr)
{
// Store the sum of all indices before i
let sum = 0;
// Store the elements that can be skipped
let count = new Map();
// Traverse the array, A[]
for(let i = 0; i < N; i++)
{
// Store the total sum of elements that
// needs to be skipped
let d = sum + arr[i] - T;
// Store the number of elements need
// to be removed
let k = 0;
if (d > 0)
{
// Traverse from the back of map so
// as to take bigger elements first
for(let u of [...count.keys()].reverse())
{
let j = u;
let x = j * count.get(j);
if (d <= x)
{
k += Math.floor((d + j - 1) / j);
break;
}
k += count.get(j);
d -= x;
}
}
// Update sum
sum += arr[i];
// Update map with the current element
if (count.has(arr[i]))
{
count.set(arr[i], count.get(i) + 1)
}
else
{
count.set(arr[i], 1)
}
document.write(k + " ");
}
}
// Driver code
// Given Input
let N = 7;
let T = 15;
let arr = [ 1, 2, 3, 4, 5, 6, 7 ];
// Function Call
skipIndices(N, T, arr);
// This code is contributed by _saurabh_jaiswal
</script>
Producción
0 0 0 0 0 2 3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar : O(N)