每次移除最小的绳索后留下的绳索-yiteyi-C++库

给定一个大小为整数的数组，N.数组包含N条长度为ropes[i]的ropes。你必须在绳子上进行切割操作，以便所有绳子都减少最小绳子的长度。显示每次切割后剩余的绳索数量。进行操作，直到每条绳索的长度变为零。注意：如果一次操作后没有绳子留下，在这种情况下，我们打印0。

null

例如：

输入：Ropes[]={5,1,1,2,3,5} 产出：4 3 2 说明：在第一次操作中，最小绳索长度为1，因此我们将所有绳索的长度减少为1，在减少后，我们留下了4根绳索，其余的绳索也是如此。

输入：Ropes[]={5,1,6,9,8,11,2,2,6,5} 产出：975321

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

简单解决方案 我们从[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++ program to print how many                       
                         // Ropes are Left After Every Cut                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function print how many Ropes are                       
                         // Left AfterEvery Cutting operation                       
                         void                                     cuttringRopes(                                     int                                     Ropes[],                                     int                                     n)                       
                         {                       
                                                 // sort all Ropes in increase                       
                                                 // of there length                       
                                                 sort(Ropes, Ropes + n);                       
           
                                                 int                                     singleOperation = 0;                       
           
                                                 // min length rope                       
                                                 int                                     cuttingLenght = Ropes[0];                       
           
                                                 // now traverse through the given                       
                                                 // Ropes in increase order of length                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 // After cutting if current rope length                       
                                                 // is greater than '0' that mean all                       
                                                 // ropes to it's right side are also                       
                                                 // greater than 0                       
                                                 if                                     (Ropes[i] - cuttingLenght > 0)                       
                                                 {                       
                                                 // print number of ropes remains                       
                                                 cout << (n - i) <<                                     " "                                     ;                       
                                   
                                                 // now current rope become                       
                                                 // min length rope                       
                                                 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

                         // Java program to print how many                       
                         // Ropes are Left After Every Cut                       
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // function print how many Ropes are Left After                       
                                                 // Every Cutting operation                       
                                                 public                                     static                                     void                                     cuttringRopes(                                     int                                     Ropes[],                                     int                                     n)                       
                                                 {                       
                                                 // sort all Ropes in increasing                       
                                                 // order of their length                       
                                                 Arrays.sort(Ropes);                       
           
                                                 int                                     singleOperation =                                     0                                     ;                       
           
                                                 // min length rope                       
                                                 int                                     cuttingLenght = Ropes[                                     0                                     ];                       
           
                                                 // now traverse through the given Ropes in                       
                                                 // increase order of length                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 {                       
                                                 // After cutting if current rope length                       
                                                 // is greater than '0' that mean all                       
                                                 // ropes to it's right side are also                       
                                                 // greater than 0                       
                                                 if                                     (Ropes[i] - cuttingLenght >                                     0                                     )                       
                                                 {                       
                                                 System.out.print(n - i +                                     " "                                     );                       
                                   
                                                 // now current rope become                       
                                                 // min length rope                       
                                                 cuttingLenght = Ropes[i];                       
           
                                                 singleOperation++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // after first operation all ropes                       
                                                 // length become zero                       
                                                 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);                       
                                                 }                       
                         }                       

C#

                         // C# program to print how many                       
                         // Ropes are Left After Every Cut                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // function print how many Ropes are Left After                       
                                                 // Every Cutting operation                       
                                                 public                                     static                                     void                                     cuttringRopes(                                     int                                     []Ropes,                                     int                                     n)                       
                                                 {                       
                                                 // sort all Ropes in increasing                       
                                                 // order of their length                       
                                                 Array.Sort(Ropes);                       
           
                                                 int                                     singleOperation = 0;                       
           
                                                 // min length rope                       
                                                 int                                     cuttingLenght = Ropes[0];                       
           
                                                 // now traverse through the given Ropes in                       
                                                 // increase order of length                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 {                       
                                                 // After cutting if current rope length                       
                                                 // is greater than '0' that mean all                       
                                                 // ropes to it's right side are also                       
                                                 // greater than 0                       
                                                 if                                     (Ropes[i] - cuttingLenght > 0)                       
                                                 {                       
                                                 Console.Write(n - i +                                     " "                                     );                       
                                   
                                                 // now current rope become                       
                                                 // min length rope                       
                                                 cuttingLenght = Ropes[i];                       
           
                                                 singleOperation++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // after first operation all ropes                       
                                                 // length become zero                       
                                                 if                                     (singleOperation == 0)                       
                                                 Console.Write(                                     "0"                                     );                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] Ropes = { 5, 1, 1, 2, 3, 5 };                       
                                                 int                                     n = Ropes.Length;                       
                                                 cuttringRopes(Ropes, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to print how many                       
                         // Ropes are Left After Every Cut                       
           
                         // Function print how many Ropes are                       
                         // Left AfterEvery Cutting operation                       
                         function                                     cuttringRopes(                                     $Ropes                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // sort all Ropes in increase                       
                                                 // of there length                       
                                                 sort(                                     $Ropes                                     );                       
           
                                                 $singleOperation                                     = 0;                       
           
                                                 // min length rope                       
                                                 $cuttingLenght                                     =                                     $Ropes                                     [0];                       
           
                                                 // now traverse through the given                       
                                                 // Ropes in increase order of length                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                   
                                                 // After cutting if current rope length                       
                                                 // is greater than '0' that mean all                       
                                                 // ropes to it's right side are also                       
                                                 // greater than 0                       
                                                 if                                     (                                     $Ropes                                     [                                     $i                                     ] -                                     $cuttingLenght                                     > 0)                       
                                                 {                       
                                                 // print number of ropes remains                       
                                                 echo                                     (                                     $n                                     -                                     $i                                     ).                                     " "                                     ;                       
                                   
                                                 // now current rope become                       
                                                 // min length rope                       
                                                 $cuttingLenght                                     =                                     $Ropes                                     [                                     $i                                     ];                       
                                                 $singleOperation                                     ++;                       
                                                 }                       
                                                 }                       
                                                 if                                     (                                     $singleOperation                                     == 0)                       
                                                 echo                                     "0 "                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $Ropes                                     =                                     array                                     (5, 1, 1, 2, 3, 5);                       
                                                 $n                                     =                                     count                                     (                                     $Ropes                                     );                       
                                                 cuttringRopes(                                     $Ropes                                     ,                                     $n                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to print how many                       
                         // Ropes are Left After Every Cut                       
           
                         // Function print how many Ropes are                       
                         // Left After Every Cutting operation                       
                         function                                     cuttringRopes(Ropes, n)                       
                         {                       
                                   
                                                 // Sort all Ropes in increasing                       
                                                 // order of their length                       
                                                 Ropes.sort();                       
           
                                                 let singleOperation = 0;                       
           
                                                 // min length rope                       
                                                 let cuttingLenght = Ropes[0];                       
           
                                                 // Now traverse through the given                       
                                                 // Ropes in increase order of length                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 {                       
                                   
                                                 // After cutting if current rope length                       
                                                 // is greater than '0' that mean all                       
                                                 // ropes to it's right side are also                       
                                                 // greater than 0                       
                                                 if                                     (Ropes[i] - cuttingLenght > 0)                       
                                                 {                       
                                                 document.write(n - i +                                     " "                                     );                       
                                   
                                                 // Now current rope become                       
                                                 // min length rope                       
                                                 cuttingLenght = Ropes[i];                       
                                   
                                                 singleOperation++;                       
                                                 }                       
                                                 }                       
                                   
                                                 // After first operation all ropes                       
                                                 // length become zero                       
                                                 if                                     (singleOperation == 0)                       
                                                 document.write(                                     "0"                                     );                       
                         }                       
           
                         // Driver Code                       
                         let Ropes = [ 5, 1, 1, 2, 3, 5 ];                       
                         let n = Ropes.length;                       
           
                         cuttringRopes(Ropes, n);                       
           
                         // This code is contributed by avijitmondal1998                       
           
                         </script>                       

4 3 2

时间复杂度：O（n长（n））空间复杂性：O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章