Dada una array arr[][] que consta de N tripletes (inicio, final, precipitación en cms), la definición de lluvia caerá desde la ubicación inicial hasta la ubicación final con la intensidad de lluvia dada en cms. También dado un número entero K y Q consultas en forma de consulta de array [] [] (En cada consulta se da X e Y ). Para cada consulta, la tarea es encontrar el número de ubicaciones entre X e Y (inclusive) que tienen precipitaciones de más de K cm.
Ejemplos:
Entrada: arr[][] = {{1, 3, 5}, {2, 8, 3}, {5, 8, 2}, {7, 9, 6}}, K = 5, consulta[][ ] ={{1, 5}, {5, 9}, {2, 9}, {1, 9}}
Salida: 4, 5, 7, 8
Explicación: la array agregada para las ubicaciones dadas será:
5 8 8 3 5 5 11 11 6 1 2 3 4 5 6 7 8 9 La array agregada informa sobre la cantidad de lluvia en cada ubicación.
De las ubicaciones 1 a 5, { 1, 2, 3, 5 } tienen precipitaciones >= 5 cm, por lo que la respuesta es 4.
De las ubicaciones 5 a 9, { 5, 6, 7, 8, 9 } tienen precipitaciones >= 5 cm , Por lo tanto, la respuesta es 5.
Desde las ubicaciones 2 a 9, { 2, 3, 5, 6, 7, 8, 9 } tienen precipitaciones >= 5 cm, Por lo tanto, la respuesta es 7.
Desde las ubicaciones 1 a 9, { 1, 2, 3, 5, 6, 7, 8, 9 } tienen lluvia >= 5 cms, por lo tanto la respuesta es 9.Entrada: arr[][] = {{2, 4, 1 }, {3, 9, 3}}, K = 5, query[][] ={{2, 5}, {4, 6}}
Salida : 3, 3
Enfoque ingenuo: recorrer la array arr[][] y encontrar el valor máximo de ubicación. Cree una array con un tamaño igual a la ubicación máxima encontrada. Luego, para cada rango de lluvia, actualice la array para obtener la array agregada. Ahora, para cada consulta, recorra la array formada y cuente el número de ubicaciones con precipitaciones superiores a K cm.
A continuación se muestra el código para el enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find number of locations
// with rainfall more than K cms
vector<int> count(vector<int> arr, vector<vector<int> > Q,
int q, int k)
{
vector<int> ans;
for (int i = 0; i < q; i++) {
int temp = 0;
for (int j = Q[i][0]; j <= Q[i][1]; j++) {
if (arr[j] >= k)
temp++;
}
ans.push_back(temp);
}
return ans;
}
// Function to find aggregate array
vector<int> aggregateArray(vector<vector<int> > arr, int n)
{
// To store the maximum location
int m = 0;
for (int i = 0; i < n; i++)
m = max(m, arr[i][1]);
// Array to store the aggregate values
vector<int> agg(m + 1);
for (int i = 0; i < n; i++) {
for (int j = arr[i][0]; j <= arr[i][1]; j++) {
agg[j] += arr[i][2];
}
}
return agg;
}
// Driver Code
int main()
{
int N = 4;
vector<vector<int> > arr = {
{ 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 }
};
// Storing aggregate array
vector<int> agg = aggregateArray(arr, N);
int Q = 4;
vector<vector<int> > queries
= { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } };
int K = 5;
vector<int> ans = count(agg, queries, Q, K);
// Printing answer to each query
for (int i = 0; i < N; i++) {
cout << ans[i] << endl;
}
}
Java
// Java program for above approach
public class GFG {
// Function to find number of locations
// with rainfall more than K cms
static int[] count(int arr[], int Q[][], int q, int k)
{
int ans[] = new int[q];
for (int i = 0; i < q; i++) {
int temp = 0;
for (int j = Q[i][0]; j <= Q[i][1]; j++) {
if (arr[j] >= k)
temp++;
}
ans[i] = temp;
}
return ans;
}
// Function to find aggregate array
static int[] aggregateArray(int arr[][], int n)
{
// To store the maximum location
int m = 0;
for (int i = 0; i < n; i++)
m = Math.max(m, arr[i][1]);
// Array to store the aggregate values
int agg[] = new int[m + 1];
for (int i = 0; i < n; i++) {
for (int j = arr[i][0]; j <= arr[i][1]; j++) {
agg[j] += arr[i][2];
}
}
return agg;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int arr[][] = { { 1, 3, 5 },
{ 2, 8, 3 },
{ 5, 8, 2 },
{ 7, 9, 6 } };
// Storing aggregate array
int agg[] = aggregateArray(arr, N);
int Q = 4;
int queries[][]
= { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } };
int K = 5;
int ans[] = count(agg, queries, Q, K);
// Printing answer to each query
for (int i = 0; i < N; i++) {
System.out.println(ans[i]);
}
}
}
// This code is contributed by phasing17
Python3
# python program for above approach # Function to find number of locations # with rainfall more than K cms def count(arr, Q, q, k): ans = [] for i in range(0, q): temp = 0 for j in range(Q[i][0], Q[i][1] + 1): if (arr[j] >= k): temp += 1 ans.append(temp) return ans # Function to find aggregate array def aggregateArray(arr, n): # To store the maximum location m = 0 for i in range(0, n): m = max(m, arr[i][1]) # Array to store the aggregate values agg = [0 for _ in range(m + 1)] for i in range(0, n): for j in range(arr[i][0], arr[i][1] + 1): agg[j] += arr[i][2] return agg # Driver Code if __name__ == "__main__": N = 4 arr = [ [1, 3, 5], [2, 8, 3], [5, 8, 2], [7, 9, 6] ] # Storing aggregate array agg = aggregateArray(arr, N) Q = 4 queries = [[1, 5], [5, 9], [2, 9], [1, 9]] K = 5 ans = count(agg, queries, Q, K) # Printing answer to each query for i in range(0, N): print(ans[i]) # This code is contributed by rakeshsahni
C#
// C# program for above approach
using System;
public class GFG {
// Function to find number of locations
// with rainfall more than K cms
static int[] count(int[] arr, int[, ] Q, int q, int k)
{
int[] ans = new int[q];
for (int i = 0; i < q; i++) {
int temp = 0;
for (int j = Q[i, 0]; j <= Q[i, 1]; j++) {
if (arr[j] >= k)
temp++;
}
ans[i] = temp;
}
return ans;
}
// Function to find aggregate array
static int[] aggregateArray(int[, ] arr, int n)
{
// To store the maximum location
int m = 0;
for (int i = 0; i < n; i++)
m = Math.Max(m, arr[i, 1]);
// Array to store the aggregate values
int[] agg = new int[m + 1];
for (int i = 0; i < n; i++) {
for (int j = arr[i, 0]; j <= arr[i, 1]; j++) {
agg[j] += arr[i, 2];
}
}
return agg;
}
// Driver code
public static void Main(string[] args)
{
int N = 4;
int[, ] arr = { { 1, 3, 5 },
{ 2, 8, 3 },
{ 5, 8, 2 },
{ 7, 9, 6 } };
// Storing aggregate array
int[] agg = aggregateArray(arr, N);
int Q = 4;
int[, ] queries
= { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } };
int K = 5;
int[] ans = count(agg, queries, Q, K);
// Printing answer to each query
for (int i = 0; i < N; i++) {
Console.WriteLine(ans[i]);
}
}
}
// This code is contributed by phasing17
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find number of locations
// with rainfall more than K cms
function count(arr, Q, q, k) {
let ans = [];
for (let i = 0; i < q; i++) {
let temp = 0;
for (let j = Q[i][0]; j <= Q[i][1]; j++) {
if (arr[j] >= k)
temp++;
}
ans.push(temp);
}
return ans;
}
// Function to find aggregate array
function aggregateArray(
arr, n)
{
// To store the maximum location
let m = 0;
for (let i = 0; i < n; i++)
m = Math.max(m, arr[i][1]);
// Array to store the aggregate values
let agg = new Array(m + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let j = arr[i][0]; j <= arr[i][1]; j++) {
agg[j] += arr[i][2];
}
}
return agg;
}
// Driver Code
let N = 4;
let arr = [
[1, 3, 5], [2, 8, 3],
[5, 8, 2], [7, 9, 6]
];
// Storing aggregate array
let agg = aggregateArray(arr, N);
let Q = 4;
let queries
= [[1, 5], [5, 9],
[2, 9], [1, 9]];
let K = 5;
let ans = count(agg, queries, Q, K);
// Printing answer to each query
for (let i = 0; i < N; i++) {
document.write(ans[i] + "<br>");
}
// This code is contributed by Potta Lokesh
</script>
Producción
4 5 7 8
Complejidad de tiempo: O(max(O(N*M), O(Q*M))).
Espacio auxiliar : O(M).
Donde N es el número de entradas, Q es el número de consultas y M es la ubicación máxima.
Enfoque eficiente: el problema dado se puede resolver utilizando el enfoque de programación de trabajo ponderado y con suma de prefijo . Este problema se puede resolver en dos partes, formando una array agregada y luego aplicando la suma de prefijos para responder consultas de manera eficiente. Siga los pasos a continuación para resolver el problema dado.
- Ordenar arr[][] según la ubicación final.
- Utilice la estructura de datos del mapa para almacenar la ubicación de inicio y el conteo de superposición.
- Para cada ubicación final, actualice la array agregada, haciendo datos de lluvia + superposición.
- Use Hashmaps para disminuir la superposición, después de cruzar la ubicación de inicio.
- Para cada triplete, actualice el Hashmap con la hora de inicio.
- Atraviese y rellene la superposición en la array hasta que se alcance la ubicación final del siguiente triplete.
- Una vez que se encuentra la array agregada, use la suma de prefijos para encontrar la respuesta a cada consulta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort
// the array in specific order
static bool comp(vector<int> a, vector<int> b)
{
return (a[1] > b[1]);
}
// Function to find number of locations
// with rainfall more than K cms
vector<int> count(vector<int> arr, vector<vector<int> > Q,
int q, int k)
{
// Prefix sum array,
// of count of locations having
// rainfall greater than k cms
int n = arr.size();
vector<int> arrPre(n);
if (arr[0] >= k)
arrPre[0] = 1;
else
arrPre[0] = 0;
for (int i = 1; i < n; i++) {
if (arr[i] >= k)
arrPre[i] = arrPre[i - 1] + 1;
else
arrPre[i] = arrPre[i - 1];
}
// evaluating the queries
vector<int> ans;
for (int i = 0; i < q; i++) {
ans.push_back(arrPre[Q[i][1]]
- arrPre[Q[i][0] - 1]);
}
return ans;
}
// Function to find aggregate array
vector<int> aggregateArray(vector<vector<int> > N, int n)
{
// To store the maximum location
int m = 0;
for (int i = 0; i < n; i++)
m = max(m, N[i][1]);
// Array to store rainfall
// of m locations sorting
// input array based on end time,
// in descending order
vector<int> arr(m + 1);
sort(N.begin(), N.end(), comp);
// To store start locn and
// rainfall corresponding to it
unordered_map<int, int> start;
int overlap = 0;
for (int i = 0; i < n; i++) {
// If two inputs have same end time,
// we need to reposition them
if (m < N[i][1])
m++;
else
// Fill m with overlap,
// till we reach current end location,
// and keep checking if we've crossed
// start time of previously recorded data
// and decrement overlap(map)
while (m > 0 && m != N[i][1])
overlap -= start[m], arr[m--] = overlap;
// To check if start time is crossed
// of previously recorded data
// and decrement overlap(map)
overlap -= start[m];
// Input data + previous recorded data
arr[m] = overlap + N[i][2];
// updating overlap with current data
overlap += N[i][2];
// storing start location with
// corresponding rainfall data
start[N[i][0] - 1] = N[i][2];
// update m
m--;
}
while (m >= N[n - 1][0])
// fill out the left out indexes
overlap -= start[m], arr[m--] = overlap;
return arr;
}
// Driver Code
int main()
{
int N = 4;
vector<vector<int> > arr = {
{ 1, 3, 5 }, { 2, 8, 3 }, { 5, 8, 2 }, { 7, 9, 6 }
};
vector<int> agg = aggregateArray(arr, N);
int Q = 4;
vector<vector<int> > queries
= { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } };
int K = 5;
vector<int> ans = count(agg, queries, Q, K);
// Printing answer to each query
for (int i = 0; i < N; i++) {
cout << ans[i] << endl;
}
}
Java
// Java program for above approach
import java.util.Arrays;
import java.util.HashMap;
public class GFG {
// Function to find number of locations
// with rainfall more than K cms
static int[] count(int arr[], int Q[][], int q, int k)
{
// Prefix sum array,
// of count of locations having
// rainfall greater than k cms
int n = arr.length;
int[] arrPre = new int[n];
if (arr[0] >= k)
arrPre[0] = 1;
else
arrPre[0] = 0;
for (int i = 1; i < n; i++) {
if (arr[i] >= k)
arrPre[i] = arrPre[i - 1] + 1;
else
arrPre[i] = arrPre[i - 1];
}
// evaluating the queries
int ans[] = new int[q];
for (int i = 0; i < q; i++) {
ans[i]
= (arrPre[Q[i][1]] - arrPre[Q[i][0] - 1]);
}
return ans;
}
// Function to find aggregate array
static int[] aggregateArray(int N[][], int n)
{
// To store the maximum location
int m = 0;
for (int i = 0; i < n; i++)
m = Math.max(m, N[i][1]);
// Array to store rainfall
// of m locations sorting
// input array based on end time,
// in descending order
int[] arr = new int[m + 1];
Arrays.sort(N, (a, b) -> - a[1] + b[1]);
// To store start locn and
// rainfall corresponding to it
HashMap<Integer, Integer> start
= new HashMap<Integer, Integer>();
int overlap = 0;
for (int i = 0; i < n; i++) {
// If two inputs have same end time,
// we need to reposition them
if (m < N[i][1])
m++;
else
// Fill m with overlap,
// till we reach current end location,
// and keep checking if we've crossed
// start time of previously recorded data
// and decrement overlap(map)
while (m > 0 && m != N[i][1]) {
overlap -= start.getOrDefault(m, 0);
arr[m--] = overlap;
}
// To check if start time is crossed
// of previously recorded data
// and decrement overlap(map)
overlap -= start.getOrDefault(m, 0);
// Input data + previous recorded data
arr[m] = overlap + N[i][2];
// updating overlap with current data
overlap += N[i][2];
// storing start location with
// corresponding rainfall data
start.put(N[i][0] - 1, N[i][2]);
// update m
m--;
}
while (m >= N[n - 1][0]) {
// fill out the left out indexes
overlap -= start.getOrDefault(m, 0);
arr[m--] = overlap;
}
return arr;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
int arr[][] = { { 1, 3, 5 },
{ 2, 8, 3 },
{ 5, 8, 2 },
{ 7, 9, 6 } };
// Storing aggregate array
int agg[] = aggregateArray(arr, N);
int Q = 4;
int queries[][]
= { { 1, 5 }, { 5, 9 }, { 2, 9 }, { 1, 9 } };
int K = 5;
int ans[] = count(agg, queries, Q, K);
// Printing answer to each query
for (int i = 0; i < N; i++) {
System.out.println(ans[i]);
}
}
}
// This code is contributed by Lovely Jain
Python3
# Python program for above approach
# Function to find number of locations
# with rainfall more than K cms
from functools import cmp_to_key
def mycmp(a, b):
return b[1] - a[1]
def count(arr, Q, q, k):
# Prefix sum array,
# of count of locations having
# rainfall greater than k cms
n = len(arr)
arrPre = [0 for i in range(n)]
if (arr[0] >= k):
arrPre[0] = 1
else:
arrPre[0] = 0
for i in range(1,n):
if (arr[i] >= k):
arrPre[i] = arrPre[i - 1] + 1
else:
arrPre[i] = arrPre[i - 1]
# evaluating the queries
ans = []
for i in range(q):
ans.append(arrPre[Q[i][1]] - arrPre[Q[i][0] - 1])
return ans
# Function to find aggregate array
def aggregateArray(N, n):
# To store the maximum location
m = 0
for i in range(n):
m = max(m, N[i][1])
# Array to store rainfall
# of m locations sorting
# input array based on end time,
# in descending order
arr = [0 for i in range(m+1)]
N.sort(key = cmp_to_key(mycmp))
# To store start locn and
# rainfall corresponding to it
start = {}
overlap = 0
for i in range(n):
# If two inputs have same end time,
# we need to reposition them
if (m < N[i][1]):
m += 1
else:
# Fill m with overlap,
# till we reach current end location,
# and keep checking if we've crossed
# start time of previously recorded data
# and decrement overlap(map)
while (m > 0 and m != N[i][1]):
overlap -= start[m] if m in start else 0
arr[m] = overlap
m -= 1
# To check if start time is crossed
# of previously recorded data
# and decrement overlap(map)
overlap -= start[m] if m in start else 0
# Input data + previous recorded data
arr[m] = overlap + N[i][2]
# updating overlap with current data
overlap += N[i][2]
# storing start location with
# corresponding rainfall data
start[N[i][0] - 1] = N[i][2]
# update m
m -= 1
while (m >= N[n - 1][0]):
# fill out the left out indexes
overlap -= start[m] if m in start else 0
arr[m] = overlap
m -= 1
return arr
# Driver Code
N = 4
arr = [
[ 1, 3, 5 ], [ 2, 8, 3 ],
[ 5, 8, 2 ], [ 7, 9, 6 ]
]
agg = aggregateArray(arr, N)
Q = 4
queries = [ [ 1, 5 ], [ 5, 9 ],
[ 2, 9 ], [ 1, 9 ] ]
K = 5
ans = count(agg, queries, Q, K)
# Printing answer to each query
for i in range(N):
print(ans[i])
# This code is contributed by shinjanpatra
Javascript
<script>
// Javascript program for above approach
// Function to find number of locations
// with rainfall more than K cms
function count(arr, Q, q, k)
{
// Prefix sum array,
// of count of locations having
// rainfall greater than k cms
var n = arr.length;
var arrPre = Array(n).fill(0);
if (arr[0] >= k)
arrPre[0] = 1;
else
arrPre[0] = 0;
for (var i = 1; i < n; i++) {
if (arr[i] >= k)
arrPre[i] = arrPre[i - 1] + 1;
else
arrPre[i] = arrPre[i - 1];
}
// evaluating the queries
var ans = [];
for (var i = 0; i < q; i++) {
ans.push(
arrPre[Q[i][1]]
- arrPre[Q[i][0] - 1]);
}
return ans;
}
// Function to find aggregate array
function aggregateArray(N, n)
{
// To store the maximum location
var m = 0;
for (var i = 0; i < n; i++)
m = Math.max(m, N[i][1]);
// Array to store rainfall
// of m locations sorting
// input array based on end time,
// in descending order
var arr = Array(m + 1).fill(0);
N.sort((a,b)=>b[1] - a[1]);
// To store start locn and
// rainfall corresponding to it
var start = new Map();
var overlap = 0;
for (var i = 0; i < n; i++) {
// If two inputs have same end time,
// we need to reposition them
if (m < N[i][1])
m++;
else
{
// Fill m with overlap,
// till we reach current end location,
// and keep checking if we've crossed
// start time of previously recorded data
// and decrement overlap(map)
while (m > 0 && m != N[i][1])
{
overlap -= start.has(m)?start.get(m):0;
arr[m--] = overlap;
}
}
// To check if start time is crossed
// of previously recorded data
// and decrement overlap(map)
overlap -= start.has(m)?start.get(m):0;
// Input data + previous recorded data
arr[m] = overlap + N[i][2];
// updating overlap with current data
overlap += N[i][2];
// storing start location with
// corresponding rainfall data
start.set(N[i][0] - 1, N[i][2]);
// update m
m--;
}
while (m >= N[n - 1][0])
{
// fill out the left out indexes
overlap -= start.has(m)?start.get(m):0;
arr[m--] = overlap;
}
return arr;
}
// Driver Code
var N = 4;
var arr = [
[ 1, 3, 5 ], [ 2, 8, 3 ],
[ 5, 8, 2 ], [ 7, 9, 6 ]
];
var agg = aggregateArray(arr, N);
var Q = 4;
var queries
= [ [ 1, 5 ], [ 5, 9 ],
[ 2, 9 ], [ 1, 9 ] ];
var K = 5;
var ans = count(agg, queries, Q, K);
// Printing answer to each query
for(var i = 0; i < N; i++) {
document.write(ans[i] + "<br>");
}
// This code is contributed by rrrtnx.
</script>
Producción
4 5 7 8
Complejidad de tiempo: O(max(NlogN, M)).
Espacio Auxiliar: O(M).
Donde N es el número de entradas y M es la ubicación máxima.
Enfoque eficiente 2 : en el enfoque anterior, primero clasificamos la array según el tiempo de finalización y luego calculamos la array agregada que toma el tiempo O (NLogN). Podemos mejorar este tiempo calculando la array agregada de la siguiente manera:
Deje que la array agregada sea agg[] .
Primero iteramos sobre cada uno de los datos de lluvia. Para cada dato ( start , end y val ), agregue val a agg[start] y reste val de agg[end+1] porque la lluvia comienza desde la posición de inicio y continúa hasta el final (inclusive).
Luego, iteramos por segunda vez sobre la array agg y realizamos un seguimiento de la lluvia actual currRain (inicializada en 0) agregando el valor de agg[index] y actualizando agg[index] como currRain .
Una vez que se crea la array agregada, use la suma de prefijos para encontrar la respuesta de cada consulta.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 program for above approach # Function to find number of locations with rainfall more than K cms def count(arr, Q, q, k): n = len(arr) # prefix sum array prefix = [0 for _ in range(n)] if arr[0] >= k: prefix[0] = 1 else: prefix[0] = 0 for i in range(1, n-1): if arr[i] >= k: prefix[i] = prefix[i-1] + 1 else: prefix[i] = prefix[i-1] # evaluate the queries using prefix sum array ans = [] for i in range(0, q): start, end = Q[i][0]-1, Q[i][1]-1 # if start is the minimum location possible, store prefix[end] if start == 0: count = prefix[end] else: count = prefix[end] - prefix[start-1] ans.append(count) return ans # Function to find aggregate array def aggregateArray(arr, n): # find maximum location possible m = -1 for data in arr: m = max(m, data[1]) # Array to store the aggregate values agg = [0 for _ in range(m + 1)] # update aggregate array at index start-1 and end locations for start, end, val in arr: agg[start-1] += val agg[end] -= val # iterate second time to fill the complete aggregate array # currRain holds amount of rainfall till current index currRain = 0 for i in range(m+1): currRain += agg[i] agg[i] = currRain return agg # Driver Code if __name__ == "__main__": N = 4 arr = [ [1, 3, 5], [2, 8, 3], [5, 8, 2], [7, 9, 6] ] # Storing aggregate array agg = aggregateArray(arr, N) Q = 4 queries = [[1, 5], [5, 9], [2, 9], [1, 9]] K = 5 ans = count(agg, queries, Q, K) # Printing answer to each query for i in range(0, N): print(ans[i]) # This code is contributed by ultrainstinct
Producción
4 5 7 8
Complejidad temporal: O(M).
Espacio Auxiliar: O(M).
Donde M es la ubicación máxima.
Publicación traducida automáticamente
Artículo escrito por aryan199598 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA