Considere una tubería de longitud L. La tubería tiene N gotas de agua en N posiciones diferentes dentro de ella. Cada gota de agua se mueve hacia el final de la tubería (x=L) a diferentes velocidades. Cuando una gota de agua se mezcla con otra gota de agua, asume la velocidad de la gota de agua con la que se está mezclando. Determine el número de gotas que salen del extremo de la tubería.
Refiérase a la figura de abajo:
Los números en los círculos indican la velocidad de las gotas de agua.
Ejemplos:
Input: length = 12, position = [10, 8, 0, 5, 3],
speed = [2, 4, 1, 1, 3]
Output: 3
Explanation:
Droplets starting at x=10 and x=8 become a droplet,
meeting each other at x=12 at time =1 sec.
The droplet starting at 0 doesn't mix with any
other droplet, so it is a drop by itself.
Droplets starting at x=5 and x=3 become a single
drop, mixing with each other at x=6 at time = 1 sec.
Note that no other droplets meet these drops before
the end of the pipe, so the answer is 3.
Refer to the figure below
Numbers on circles indicates speed of water droplets.
Enfoque:
Este problema utiliza la técnica codiciosa .
Una gota se mezclará con otra gota si se cumplen dos condiciones:
1. Si la gota es más rápida que la gota con la que se mezcla
2. Si la posición de la gota más rápida está detrás de la gota más lenta.
Usamos una array de pares para almacenar la posición y el tiempo que tardaría la i -ésima caída en llegar al final de la tubería. Luego ordenamos la array según la posición de las gotas. Ahora tenemos una idea clara de qué gotas se encuentran detrás de qué gotas y su respectivo tiempo necesario para llegar al final. Más tiempo significa menos velocidad y menos tiempo significa más velocidad. Ahora todas las gotas antes de una gota más lenta se mezclarán con él. Y todas las gotas después de la gota más lenta se mezclan con la siguiente gota más lenta y así sucesivamente.
Por ejemplo, si los tiempos para llegar al final son: 12, 3, 7, 8, 1 (ordenados según las posiciones)
La gota 0 es la más lenta, no se mezclará con la gota siguiente
La primera gota es más rápida que la segunda, por lo que se mezclarán y la segunda gota es más rápida que la tercera, por lo que las tres se mezclarán. No pueden mezclarse con la cuarta gota porque es más rápida.
No de máximo local + residuo (gotas después del último máximo local) = Número total de gotas.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find the number
// of the drops that come out of the
// pipe
int drops(int length, int position[],
int speed[], int n)
{
// stores position and time
// taken by a single
// drop to reach the end as a pair
vector<pair<int, double> > m(n);
int i;
for (i = 0; i < n; i++) {
// calculates distance needs to be
// covered by the ith drop
int p = length - position[i];
// inserts initial position of the
// ith drop to the pair
m[i].first = position[i];
// inserts time taken by ith
// drop to reach
// the end to the pair
m[i].second = p * 1.0 / speed[i];
}
// sorts the pair according to increasing
// order of their positions
sort(m.begin(), m.end());
int k = 0; // counter for no of final drops
int curr_max = m[n-1].second;
// we traverse the array demo
// right to left
// to determine the slower drop
for (i = n - 2; i >= 0; i--)
{
// checks for next slower drop
if (m[i].second > curr_max)
{
k++;
curr_max=m[i].second;
}
}
// calculating residual
// drops in the pipe
k++;
return k;
}
// Driver Code
int main()
{
// length of pipe
int length = 12;
// position of droplets
int position[] = { 10, 8, 0, 5, 3 };
// speed of each droplets
int speed[] = { 2, 4, 1, 1, 3 };
int n = sizeof(speed)/sizeof(speed[0]);
cout << drops(length, position, speed, n);
return 0;
}
Java
import java.util.*;
// User defined Pair class
class Pair {
int x;
int y;
// Constructor
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// class to define user defined conparator
class Compare {
static void compare(Pair arr[], int n)
{
// Comparator to sort the pair according to second element
Arrays.sort(arr, new Comparator<Pair>() {
@Override public int compare(Pair p1, Pair p2)
{
return p1.x - p2.x;
}
});
}
}
public class Main
{
// Function to find the number
// of the drops that come out of the
// pipe
static int drops(int length, int[] position, int[] speed, int n)
{
// stores position and time
// taken by a single
// drop to reach the end as a pair
Pair m[] = new Pair[n];
int i;
for (i = 0; i < n; i++)
{
// calculates distance needs to be
// covered by the ith drop
int p = length - position[i];
// inserts initial position of the
// ith drop to the pair
// inserts time taken by ith
// drop to reach
// the end to the pair
m[i] = new Pair(position[i], p / speed[i]);
}
// sorts the pair according to increasing
// order of their positions
Compare obj = new Compare();
obj.compare(m, n);
int k = 0; // counter for no of final drops
int curr_max = (int)(m[n - 1].y);
// we traverse the array demo
// right to left
// to determine the slower drop
for (i = n - 2; i >= 0; i--)
{
// checks for next slower drop
if (m[i].y > curr_max)
{
k++;
curr_max = (int)(m[i].y);
}
}
// calculating residual
// drops in the pipe
k++;
return k;
}
public static void main(String[] args) {
// length of pipe
int length = 12;
// position of droplets
int[] position = { 10, 8, 0, 5, 3 };
// speed of each droplets
int[] speed = { 2, 4, 1, 1, 3 };
int n = speed.length;
System.out.println(drops(length, position, speed, n));
}
}
// This code is contributed by decode2207.
Python3
# Function to find the number # of the drops that come out of the # pipe def drops(length, position, speed, n): # Stores position and time # taken by a single drop to # reach the end as a pair m = [] for i in range(n): # Calculates distance needs to be # covered by the ith drop p = length - position[i] # Inserts initial position of the # ith drop to the pair # inserts time taken by ith # drop to reach # the end to the pair m.append([position[i], (p * 1.0) / speed[i]]) # Sorts the pair according to increasing # order of their positions m.sort() # Counter for no of final drops k = 0 curr_max = m[n - 1][1] # We traverse the array demo # right to left # to determine the slower drop for i in range(n - 2, -1, -1): # Checks for next slower drop if (m[i][1] > curr_max): k += 1 curr_max = m[i][1] # Calculating residual # drops in the pipe k += 1 return k # Driver Code # Length of pipe length = 12 # Position of droplets position = [ 10, 8, 0, 5, 3 ] # Speed of each droplets speed = [ 2, 4, 1, 1, 3 ] n = len(speed) print(drops(length, position, speed, n)) # This code is contributed by divyeshrabadiya07
C#
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the number
// of the drops that come out of the
// pipe
static int drops(int length, int[] position,
int[] speed, int n)
{
// stores position and time
// taken by a single
// drop to reach the end as a pair
List<Tuple<int,double>> m = new List<Tuple<int,double>>();
int i;
for (i = 0; i < n; i++)
{
// calculates distance needs to be
// covered by the ith drop
int p = length - position[i];
// inserts initial position of the
// ith drop to the pair
// inserts time taken by ith
// drop to reach
// the end to the pair
m.Add(new Tuple<int,double>(position[i], p * 1.0 / speed[i]));
}
// sorts the pair according to increasing
// order of their positions
m.Sort();
int k = 0; // counter for no of final drops
int curr_max = (int)m[n - 1].Item2;
// we traverse the array demo
// right to left
// to determine the slower drop
for (i = n - 2; i >= 0; i--)
{
// checks for next slower drop
if (m[i].Item2 > curr_max)
{
k++;
curr_max = (int)m[i].Item2;
}
}
// calculating residual
// drops in the pipe
k++;
return k;
}
// Driver code
static void Main()
{
// length of pipe
int length = 12;
// position of droplets
int[] position = { 10, 8, 0, 5, 3 };
// speed of each droplets
int[] speed = { 2, 4, 1, 1, 3 };
int n = speed.Length;
Console.WriteLine(drops(length, position, speed, n));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Function to find the number
// of the drops that come out of the
// pipe
function drops(length, position, speed, n)
{
// stores position and time
// taken by a single
// drop to reach the end as a pair
var m = Array.from(Array(n), ()=>Array(2));
var i;
for (i = 0; i < n; i++) {
// calculates distance needs to be
// covered by the ith drop
var p = length - position[i];
// inserts initial position of the
// ith drop to the pair
m[i][0] = position[i];
// inserts time taken by ith
// drop to reach
// the end to the pair
m[i][1] = p * 1.0 / speed[i];
}
// sorts the pair according to increasing
// order of their positions
m.sort();
var k = 0; // counter for no of final drops
var curr_max = m[n-1][1];
// we traverse the array demo
// right to left
// to determine the slower drop
for (i = n - 2; i >= 0; i--)
{
// checks for next slower drop
if (m[i][1] > curr_max)
{
k++;
curr_max=m[i][1];
}
}
// calculating residual
// drops in the pipe
k++;
return k;
}
// Driver Code
// length of pipe
var length = 12;
// position of droplets
var position = [10, 8, 0, 5, 3];
// speed of each droplets
var speed = [2, 4, 1, 1, 3];
var n = speed.length;
document.write( drops(length, position, speed, n));
</script>
3
Complejidad de Tiempo: O(nlog(n))
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por agnivakolay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA