Рубрики

Веревки, оставленные после каждого удаления самых маленьких

Учитывая массив целого числа размера, N. Array содержит N веревок длины Ropes [i]. Вы должны выполнить операцию разрезания на веревках так, чтобы все они были уменьшены на длину самой маленькой веревки. Покажите количество веревок, оставшихся после каждого разреза. Выполняйте операции, пока длина каждой веревки не станет равной нулю.
Примечание. Если после одной операции не осталось веревок, в этом случае мы печатаем 0.

Примеры:

Input : Ropes[] = { 5, 1, 1, 2, 3, 5 }
Output : 4 3 2
Explanation : In first operation the minimum ropes is 1 so we reduce length 1 from all of them after reducing we left with 4 ropes and we do same for rest.

Input : Ropes[] = { 5, 1, 6, 9, 8, 11, 2, 2, 6, 5 }
Output : 9 7 5 3 2 1

Простое решение состоит в том, чтобы пройти цикл из [0… n-1], в каждой итерации сначала мы находим веревку минимальной длины. После этого мы уменьшаем длину всех веревок и затем подсчитываем, сколько осталось веревок, длина которых больше нуля. этот процесс выполняется до тех пор, пока длина всех канатов не станет больше нуля. Это решение работает за O (n 2 ) раз.

Эффективное решение работает в O (nlog (n)). Сначала мы должны отсортировать все веревки в порядке возрастания их длины. после этого мы должны следовать за шагом.

//initial cutting length "min rope"  
CuttingLength = Ropes[0]
Now Traverse a loop from left to right [1...n]
 .During traverse we check that 
  is current ropes length is greater than zero or not 
 IF ( Ropes[i] - CuttingLength > 0 ) 
 .... IF Yes then all ropes to it's right side also greater than 0
 .... Print number of ropes remains (n - i)
 ....update Cutting Length by current rope length
 ...... CuttingLength = Ropes[i]          
Do the same process for the rest.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для печати сколько
// Веревки остаются после каждого разреза
#include <bits/stdc++.h>

using namespace std;

  
// Функция print сколько канатов
// Left AfterEvery Операция резки

void cuttringRopes(int Ropes[], int n)

{

    // сортируем все веревки по возрастанию

    // длины

    sort(Ropes, Ropes + n);

  

    int singleOperation = 0;

  

    // минимальная длина веревки

    int cuttingLenght = Ropes[0];

  

    // теперь проходим через данный

    // Канаты в порядке увеличения длины

    for (int i = 1; i < n; i++)

    {

        // После обрезки, если текущая длина веревки

        // больше 0, что означает все

        // верёвки к правой стороне тоже

        // больше 0

        if (Ropes[i] - cuttingLenght > 0)

        {

            // выводим количество остатков канатов

            cout << (n - i) << " ";

              

            // теперь текущая веревка становится

            // минимальная длина веревки

            cuttingLenght = Ropes[i];

            singleOperation++;

        }

    }

    if (singleOperation == 0)

        cout << "0 ";

}

int main()

{

    int Ropes[] = { 5, 1, 1, 2, 3, 5 };

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

    cuttringRopes(Ropes, n);

    return 0;

}

Джава

// Java программа для печати сколько
// Веревки остаются после каждого разреза

import java.util.*;

import java.lang.*;

import java.io.*;

  

class GFG {

      

    // функция print, сколько веревок осталось после

    // Каждая операция резки

    public static void cuttringRopes(int Ropes[], int n)

    {

        // сортируем все верёвки по возрастанию

        // порядок их длины

        Arrays.sort(Ropes);

  

        int singleOperation = 0;

  

        // минимальная длина веревки

        int cuttingLenght = Ropes[0];

  

        // теперь проходим через указанные Веревки в

        // увеличиваем порядок длины

        for (int i = 1; i < n; i++)

        {

            // После обрезки, если текущая длина веревки

            // больше 0, что означает все

            // верёвки к правой стороне тоже

            // больше 0

            if (Ropes[i] - cuttingLenght > 0)

            {

                System.out.print(n - i + " ");

                  

                // теперь текущая веревка становится

                // минимальная длина веревки

                cuttingLenght = Ropes[i];

  

                singleOperation++;

            }

        }

          

        // после первой операции все канаты

        // длина становится нулевой

        if (singleOperation == 0)

            System.out.print("0");

    }

  

    public static void main(String[] arg)

    {

        int[] Ropes = { 5, 1, 1, 2, 3, 5 };

        int n = Ropes.length;

        cuttringRopes(Ropes, n);

    }

}

python3

# Python 3 программа для
# напечатать сколько
# Веревки остались после
# Каждое сокращение

  
# Функция вывести, сколько канатов
# Left AfterEvery Операция резки

def cuttringRopes(Ropes, n) :

  

    # сортировать все верёвки по возрастанию

    # там длины

    Ropes.sort()

   

    singleOperation = 0

   

    # минимальная длина веревки

    cuttingLenght = Ropes[0]

   

    # теперь пройти через данный

    # Канаты в порядке увеличения длины

    for i in range(1,n) :

  

        # После резки, если текущая длина веревки

        # больше '0', что означает все

        # верёвки к правой стороне тоже

        # больше 0

        if (Ropes[i] - cuttingLenght > 0) :

  

            # распечатать количество оставшихся веревок

            print((n - i) ,end= " ")

               

            # теперь текущие веревки становятся

            # минимальная длина веревки

            cuttingLenght = Ropes[i]

            singleOperation = singleOperation + 1

          

          

    if (singleOperation == 0) :

        print("0 ",end="")

  

  

Ropes = [ 5, 1, 1, 2, 3, 5 ]

n = len(Ropes)

cuttringRopes(Ropes, n)

  

  

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для печати сколько
// Веревки остаются после каждого разреза

using System;

  

class GFG {

      

    // функция print, сколько веревок осталось после

    // Каждая операция резки

    public static void cuttringRopes(int []Ropes, int n)

    {

        // сортируем все верёвки по возрастанию

        // порядок их длины

        Array.Sort(Ropes);

  

        int singleOperation = 0;

  

        // минимальная длина веревки

        int cuttingLenght = Ropes[0];

  

        // теперь проходим через указанные Веревки в

        // увеличиваем порядок длины

        for (int i = 1; i < n; i++)

        {

            // После обрезки, если текущая длина веревки

            // больше 0, что означает все

            // верёвки к правой стороне тоже

            // больше 0

            if (Ropes[i] - cuttingLenght > 0)

            {

                Console.Write(n - i + " ");

                  

                // теперь текущая веревка становится

                // минимальная длина веревки

                cuttingLenght = Ropes[i];

  

                singleOperation++;

            }

        }

          

        // после первой операции все канаты

        // длина становится нулевой

        if (singleOperation == 0)

            Console.Write("0");

    }

  

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

    public static void Main()

    {

        int[] Ropes = { 5, 1, 1, 2, 3, 5 };

        int n = Ropes.Length;

        cuttringRopes(Ropes, n);

    }

}

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

PHP

<?php
// PHP программа для печати сколько
// Веревки остаются после каждого разреза

  
// Функция print сколько канатов
// Left AfterEvery Операция резки

function cuttringRopes($Ropes, $n)

{

      

    // сортируем все веревки по возрастанию

    // длины

    sort($Ropes);

  

    $singleOperation = 0;

  

    // минимальная длина веревки

    $cuttingLenght = $Ropes[0];

  

    // теперь проходим через данный

    // Канаты в порядке увеличения длины

    for ($i = 1; $i < $n; $i++)

    {

          

        // После обрезки, если текущая длина веревки

        // больше 0, что означает все

        // верёвки к правой стороне тоже

        // больше 0

        if ($Ropes[$i] - $cuttingLenght > 0)

        {

            // выводим количество остатков канатов

            echo ($n - $i). " ";

              

            // теперь текущая веревка становится

            // минимальная длина веревки

            $cuttingLenght = $Ropes[$i];

            $singleOperation++;

        }

    }

    if ($singleOperation == 0)

        echo "0 ";

}

  

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

    $Ropes = array(5, 1, 1, 2, 3, 5);

    $n = count($Ropes);

    cuttringRopes($Ropes, $n);

  
// Этот код предоставлен Sam007
?>

4 3 2 

Сложность времени: O (n long (n))
Пространство сложность: O (1)

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

Веревки, оставленные после каждого удаления самых маленьких

0.00 (0%) 0 votes