Рубрики

Найти первый круговой тур, который посещает все бензиновые насосы

Предположим, что есть круг. На этом круге есть n бензонасосов. Вам предоставляется два набора данных.

  1. Количество бензина, которое есть у каждого бензонасоса.
  2. Расстояние от этого бензонасоса до следующего бензонасоса.

Рассчитайте первую точку, откуда грузовик сможет пройти круг (грузовик остановится у каждого бензонасоса, и у него будет бесконечная вместимость). Ожидаемая сложность времени O (n). Предположим, что для 1-литрового бензина грузовик может проехать 1 единицу расстояния.

Например, пусть есть 4 бензиновых насоса с количеством бензина и расстоянием до следующих пар значений бензиновых насосов: {4, 6}, {6, 5}, {7, 3} и {4, 5}. Первым пунктом, откуда грузовик может совершить круговой тур, является 2-й бензонасос. Выход должен быть «start = 1» (индекс 2-го бензонасоса).

Простое решение — рассмотреть каждый бензонасос в качестве отправной точки и посмотреть, есть ли возможный тур. Если мы находим отправную точку с возможным решением, мы возвращаем эту отправную точку. Наихудшая временная сложность этого решения — O (n ^ 2).

Эффективный подход заключается в использовании очереди для хранения текущего тура. Сначала мы ставим в очередь первый бензонасос в очередь, мы продолжаем ставить бензиновые насосы в очередь до тех пор, пока не закончим тур или пока текущее количество бензина не станет отрицательным. Если сумма становится отрицательной, мы продолжаем снимать бензин с насосов до тех пор, пока очередь не опустеет.

Вместо создания отдельной очереди мы используем сам данный массив в качестве очереди. Мы поддерживаем две индексные переменные start и end, которые представляют заднюю и переднюю часть очереди.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ программа для поиска кругового тура для грузовика
#include <bits/stdc++.h>

using namespace std; 

  
// Бензиновый насос имеет бензин и расстояние до следующего бензонасоса

class petrolPump 

{

    public:

    int petrol; 

    int distance; 

}; 

  
// Функция возвращает начальную точку, если есть возможное решение,
// в противном случае возвращает -1

int printTour(petrolPump arr[], int n) 

    // Рассмотрим первый бензонасос в качестве отправной точки

    int start = 0; 

    int end = 1; 

  

    int curr_petrol = arr[start].petrol - arr[start].distance; 

  

    / * Запустить петлю, пока все бензиновые насосы не посещены.

    И мы снова достигли первого бензонасоса с 0 или более бензином * /

    while (end != start || curr_petrol < 0) 

    

        // Если текущее количество бензина в грузовике становится меньше 0, то

        // снимаем стартовый бензонасос с тура

        while (curr_petrol < 0 && start != end) 

        

            // Снимите пусковой бензонасос. Изменить начало

            curr_petrol -= arr[start].petrol - arr[start].distance; 

            start = (start + 1) % n; 

  

            // Если 0 рассматривается как начало заново, то нет

            // возможное решение

            if (start == 0) 

            return -1; 

        

  

        // Добавить бензонасос в текущий тур

        curr_petrol += arr[end].petrol - arr[end].distance; 

  

        end = (end + 1) % n; 

    

  

    // Возвращаем начальную точку

    return start; 

  
// Код драйвера

int main() 

    petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}}; 

  

    int n = sizeof(arr)/sizeof(arr[0]); 

    int start = printTour(arr, n); 

  

    (start == -1)? cout<<"No solution": cout<<"Start = "<<start; 

  

    return 0; 

  

  
// Этот код предоставлен rathbhupendra

С

// C программа для поиска кругового тура для грузовика
#include <stdio.h>

  
// Бензиновый насос имеет бензин и расстояние до следующего бензонасоса

struct petrolPump

{

  int petrol;

  int distance;

};

  
// Функция возвращает начальную точку, если есть возможное решение,
// в противном случае возвращает -1

int printTour(struct petrolPump arr[], int n)

{

    // Рассмотрим первый бензонасос в качестве отправной точки

    int start = 0;

    int end =  1;

  

    int curr_petrol = arr[start].petrol - arr[start].distance;

  

    / * Запустить петлю, пока все бензиновые насосы не посещены.

      И мы снова достигли первого бензонасоса с 0 или более бензином * /

    while (end != start || curr_petrol < 0)

    {

        // Если текущее количество бензина в грузовике становится меньше 0, то

        // снимаем стартовый бензонасос с тура

        while (curr_petrol < 0 && start != end)

        {

            // Снимите пусковой бензонасос. Изменить начало

            curr_petrol -= arr[start].petrol - arr[start].distance;

            start = (start + 1)%n;

  

            // Если 0 рассматривается как начало заново, то нет

            // возможное решение

            if (start == 0)

               return -1;

        }

  

        // Добавить бензонасос в текущий тур

        curr_petrol += arr[end].petrol - arr[end].distance;

  

        end = (end + 1)%n;

    }

  

    // Возвращаем начальную точку

    return start;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct petrolPump arr[] = {{6, 4}, {3, 6}, {7, 3}};

  

    int n = sizeof(arr)/sizeof(arr[0]);

    int start = printTour(arr, n);

  

    (start == -1)? printf("No solution"): printf("Start = %d", start);

  

    return 0;

}

Джава

// Java программа для поиска кругового тура для грузовика

  

public class Petrol 

{

    // Бензиновый насос имеет бензин и расстояние до следующего бензонасоса

    static class petrolPump

    {

        int petrol;

        int distance;

          

        // конструктор

        public petrolPump(int petrol, int distance) 

        {

            this.petrol = petrol;

            this.distance = distance;

        }

    }

      

    // Функция возвращает начальную точку, если есть возможное решение,

    // в противном случае возвращает -1

    static int printTour(petrolPump arr[], int n)

    {  

        int start = 0;

        int end = 1;

        int curr_petrol = arr[start].petrol - arr[start].distance;

          

        // Если текущее количество бензина в грузовике становится меньше 0, то

        // снимаем стартовый бензонасос с тура

        while(end != start || curr_petrol < 0)

        {

              

            // Если текущее количество бензина в грузовике становится меньше 0, то

            // снимаем стартовый бензонасос с тура

            while(curr_petrol < 0 && start != end)

            {

                // Снимите пусковой бензонасос. Изменить начало

                curr_petrol -= arr[start].petrol - arr[start].distance;

                start = (start + 1) % n;

                  

                // Если 0 рассматривается как начало заново, то нет

                // возможное решение

                if(start == 0)

                    return -1;

            }

            // Добавить бензонасос в текущий тур

            curr_petrol += arr[end].petrol - arr[end].distance;

              

            end = (end + 1)%n;

        }

          

        // Возвращаем начальную точку

        return start;

    }

      

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

          

        petrolPump[] arr = {new petrolPump(6, 4),

                            new petrolPump(3, 6),

                            new petrolPump(7, 3)};

          

        int start = printTour(arr, arr.length);

          

        System.out.println(start == -1 ? "No Solution" : "Start = " + start); 

  

    }

  
}
// Этот код предоставлен Sumit Ghosh

питон

# Программа Python для поиска кругового тура по треку

  
# У бензонасоса есть бензин и расстояние до следующего бензинового сутенера

class PetrolPump:

      

    # Конструктор для создания нового узла

    def __init__(self,petrol, distance):

        self.petrol = petrol

        self.distance = distance 

  
# Начальная точка возврата функции, если есть возможность
# решение в противном случае возвращает -1

def printTour(arr):

      

    n = len(arr)

    # Рассмотрим первый бензонасос в качестве отправной точки

    start = 0 

    end = 1 

      

    curr_petrol = arr[start].petrol - arr[start].distance 

      

    # Запустите цикл пока все бензиновые насосы не посещаются

    # И мы снова достигли первого бензонасоса с 0

    # или больше бензина

    while(end != start or curr_petrol < 0 ):

          

        # Если текущее количество бензиновых насосов не посещается

        # И мы снова достигли первого бензонасоса с

        # 0 или больше бензина

        while(curr_petrol < 0 and start != end):

              

            # Снимите пусковой бензонасос. Изменить начало

            curr_petrol -= arr[start].petrol - arr[start].distance

            start = (start +1)%n

              

            # Если 0 считается начальным снова, то

            # нет возможного решения

            if start == 0:

                return -1

  

        # Добавить бензонасос в текущий тур

        curr_petrol += arr[end].petrol - arr[end].distance 

          

        end = (end +1) % n

  

    return start 

  
# Программа драйвера для проверки вышеуказанной функции

arr = [PetrolPump(6,4), PetrolPump(3,6), PetrolPump(7,3)]

start = printTour(arr)

  

print "No solution" if start == -1 else "start =", start

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для поиска циркуляра
// тур для грузовика

using System;

  

class GFG

{

    // бензиновый насос имеет бензин и

    // расстояние до следующего бензонасоса

    public class petrolPump

    {

        public int petrol;

        public int distance;

  

        // конструктор

        public petrolPump(int petrol, 

                          int distance)

        {

            this.petrol = petrol;

            this.distance = distance;

        }

    }

  

    // Функция возвращает начальную точку

    // если есть возможное решение,

    // в противном случае возвращает -1

    public static int printTour(petrolPump[] arr, 

                                int n)

    {

        int start = 0;

        int end = 1;

        int curr_petrol = arr[start].petrol - 

                          arr[start].distance;

  

        // Если текущее количество бензина в

        // грузовик становится меньше 0, тогда

        // снимаем стартовый бензонасос с тура

        while (end != start || curr_petrol < 0)

        {

  

            // Если текущее количество бензина в

            // грузовик становится меньше 0, тогда

            // снимаем стартовый бензонасос с тура

            while (curr_petrol < 0 && start != end)

            {

                // Снимите пусковой бензонасос.

                // Изменить начало

                curr_petrol -= arr[start].petrol - 

                               arr[start].distance;

                start = (start + 1) % n;

  

                // Если 0 рассматривается как

                // начать заново, то нет

                // возможное решение

                if (start == 0)

                {

                    return -1;

                }

            }

              

            // Добавить бензонасос в текущий тур

            curr_petrol += arr[end].petrol - 

                           arr[end].distance;

  

            end = (end + 1) % n;

        }

  

        // Возвращаем начальную точку

        return start;

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

        petrolPump[] arr = new petrolPump[]

        {

            new petrolPump(6, 4),

            new petrolPump(3, 6),

            new petrolPump(7, 3)

        };

  

        int start = printTour(arr, arr.Length);

  

        Console.WriteLine(start == -1 ? "No Solution"

                                   "Start = " + start);

    }

}

  
// Этот код предоставлен Shrikant13

Выход:

start = 2

Сложность времени: на первый взгляд кажется более чем линейной. Если мы рассмотрим элементы между началом и концом как часть круговой очереди, мы можем заметить, что каждый элемент ставится в очередь не более двух раз в очередь. Общее количество операций пропорционально общему количеству операций постановки в очередь. Следовательно, временная сложность составляет O (n) .

Вспомогательное пространство: O (1)

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти первый круговой тур, который посещает все бензиновые насосы

0.00 (0%) 0 votes