每次取下最小的鋼絲繩后剩下的鋼絲繩 · GeeksForGeeks 中文系列教程

# 每次取下最小的鋼絲繩后剩下的鋼絲繩 > 原文： [https://www.geeksforgeeks.org/ropes-left-every-cut/](https://www.geeksforgeeks.org/ropes-left-every-cut/) 給定一個大小為整數的數組，N 個。數組包含 N 條長度為 Ropes [i]的繩索。您必須對繩索進行切割操作，以使所有繩索均減小最小繩索的長度。顯示每次切割后剩余的繩索數量。進行操作，直到每條繩索的長度變為零。注意：如果單次操作后沒有剩余繩子，在這種情況下，我們將打印 0。 **示例**： > 輸入：Ropes [] = {5，1，1，2，3，5} > 輸出：4 3 2 > 說明：在第一個操作中，最小繩索為 1，因此我們將所有長度的長度都減少 1 減少我們剩下的 4 條繩索，我們會做同樣的休息。 > > 輸入：Ropes [] = {5，1，6，9，8，11，2，2，6，6，5} > 輸出：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++ ```cpp // 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; } ```