Dado un mapa de la ciudad y el alcance de la red, la tarea es determinar el número mínimo de torres para que cada casa esté dentro del alcance de al menos una torre. Cada torre debe instalarse encima de una casa existente.
Ejemplos:
Input: range : 1 house : 1 2 3 4 5 Output: 2 Input: range : 2 house : 7 2 4 6 5 9 12 11 Output: 3
Todas las ciudades se pueden cubrir insertando 2 torres, es decir, en la casa 2 y 4.
Todas las ciudades se pueden cubrir insertando 3 torres, es decir, en las casas 4, 9 y 12.
Algoritmo: –
- Primero, ordena todos los elementos.
- Cuente solo una vez y luego atraviese hasta su casa central.
- Después de esto, atraviese nuevamente hasta el rango de la torre.
- Nuevamente repita los pasos 1, 2, 3 hasta que todas las casas estén cubiertas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to count the number of tower int number_of_tower(int house[], int range, int n) { // first we sort the house numbers sort(house, house + n); // for count number of towers int numOfTower = 0; // for iterate all houses int i = 0; while (i < n) { // count number of towers numOfTower++; // find the middle location int loc = house[i] + range; // traverse till middle location while (i < n && house[i] <= loc) i++; // this is point to middle // house where we insert the tower --i; // now find the last location loc = house[i] + range; // traverse till last house of the range while (i < n && house[i] <= loc) i++; } // return the number of tower return numOfTower; } // Driver code int main() { // given elements int house[] = { 7, 2, 4, 6, 5, 9, 12, 11 }; int range = 2; int n = sizeof(house) / sizeof(house[0]); // print number of towers cout << number_of_tower(house, range, n); }
Java
// Java implementation of above approach import java.util.Arrays; public class Improve { // Function to count the number of tower static int number_of_tower(int house[], int range, int n) { // first we sort the house numbers Arrays.sort(house); // for count number of towers int numOfTower = 0; // for iterate all houses int i = 0; while (i < n) { // count number of towers numOfTower++; // find the middle location int loc = house[i] + range; // traverse till middle location while (i < n && house[i] <= loc) i++; // this is point to middle // house where we insert the tower --i; // now find the last location loc = house[i] + range; // traverse till last house of the range while (i < n && house[i] <= loc) i++; } // return the number of tower return numOfTower; } public static void main(String args[]) { // given elements int house[] = { 7, 2, 4, 6, 5, 9, 12, 11 }; int range = 2; int n = house.length; // print number of towers System.out.println(number_of_tower(house, range, n)); } // This code is contributed by ANKITRAI1 }
Python 3
# Python 3 implementation of # above approach # Function to count the # number of tower def number_of_tower(house, r, n): # first we sort the house numbers house.sort() # for count number of towers numOfTower = 0 # for iterate all houses i = 0 while (i < n) : # count number of towers numOfTower += 1 # find the middle location loc = house[i] + r # traverse till middle location while (i < n and house[i] <= loc): i += 1 # this is point to middle # house where we insert the tower i -= 1 # now find the last location loc = house[i] + r # traverse till last house # of the range while (i < n and house[i] <= loc): i += 1 # return the number of tower return numOfTower # Driver code if __name__ == "__main__": # given elements house = [ 7, 2, 4, 6, 5, 9, 12, 11 ] r = 2 n = len(house) # print number of towers print(number_of_tower(house, r, n)) # This code is contributed # by ChitraNayal
C#
// C# implementation of above approach using System; public class Improve { // Function to count the number of tower static int number_of_tower(int []house, int range, int n) { // first we sort the house numbers Array.Sort(house); // for count number of towers int numOfTower = 0; // for iterate all houses int i = 0; while (i < n) { // count number of towers numOfTower++; // find the middle location int loc = house[i] + range; // traverse till middle location while (i < n && house[i] <= loc) i++; // this is point to middle // house where we insert the tower --i; // now find the last location loc = house[i] + range; // traverse till last house of the range while (i < n && house[i] <= loc) i++; } // return the number of tower return numOfTower; } public static void Main() { // given elements int []house = { 7, 2, 4, 6, 5, 9, 12, 11 }; int range = 2; int n = house.Length; // print number of towers Console.WriteLine(number_of_tower(house, range, n)); // This code is contributed by inder_verma.. } }
PHP
<?php //PHP implementation of above approach // Function to count the number of tower function number_of_tower($house, $range, $n) { // first we sort the house numbers sort($house); // for count number of towers $numOfTower = 0; // for iterate all houses $i = 0; while ($i < $n) { // count number of towers $numOfTower++; // find the middle location $loc = $house[$i] + $range; // traverse till middle location while ($i < $n && $house[$i] <= $loc) $i++; // this is point to middle // house where we insert the tower --$i; // now find the last location $loc = $house[$i] + $range; // traverse till last house of the range while ($i < $n && $house[$i] <= $loc) $i++; } // return the number of tower return $numOfTower; } // Driver code // given elements $house = array( 7, 2, 4, 6, 5, 9, 12, 11 ); $range = 2; $n = sizeof($house) / sizeof($house[0]); // print number of towers echo number_of_tower($house, $range, $n); // This code is contributed by Sachin. ?>
Javascript
<script> // JavaScript implementation of above approach // Function to count the number of tower function number_of_tower(house,range,n) { // first we sort the house numbers house.sort(function(a,b){return a-b;}); // for count number of towers let numOfTower = 0; // for iterate all houses let i = 0; while (i < n) { // count number of towers numOfTower++; // find the middle location let loc = house[i] + range; // traverse till middle location while (i < n && house[i] <= loc) i++; // this is point to middle // house where we insert the tower --i; // now find the last location loc = house[i] + range; // traverse till last house of the range while (i < n && house[i] <= loc) i++; } // return the number of tower return numOfTower; } // given elements let house=[7, 2, 4, 6, 5, 9, 12, 11]; let range = 2; let n = house.length; // print number of towers document.write(number_of_tower(house, range, n)); // This code is contributed by avanitrachhadiya2155 </script>
Producción:
3
Complejidad de tiempo: O(nlogn)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por DevanshuAgarwal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA