每次移除最短繩索後剩餘的繩索

---

在本文中，我們將討論解決“每次移除最短繩索後剩餘的繩索”問題的兩種方法。

問題陳述

給定一個元素陣列，其中 array[i] 表示陣列中第 i 條繩索的長度。我們的任務是從陣列的所有元素中剪掉等於陣列中最小的元素的長度，直到所有元素的長度都等於零。我們必須輸出每次剪下操作後長度不為零的繩索數量。

讓我們考慮一個相同的例子 -

假設陣列長度為 10，陣列中的元素（即每條繩索的長度）為 -

ropes[] = { 5, 1, 6, 9, 8, 11, 2, 2, 6, 5 }

對於第一次迭代，我們在索引 1 處有最短的繩索

從繩索中剪掉 1 個單位長度，並將零長度繩索從陣列中刪除後，得到的新陣列為 -

ropes[] = { 4, 5, 8, 7, 10, 1, 1, 5, 4 }
and number of ropes left = 9

現在我們在索引 5 和 6 處有最短的繩索，長度為 1 個單位。

從所有繩索中剪掉 1 個單位長度，並將零長度繩索刪除後，得到的新陣列為 -

ropes[] = { 3, 4, 7, 6, 9, 4, 3 }
and number of ropes left = 7

類似地，在執行相同的操作直到我們得到一個空陣列後，後續的陣列長度為 - 9、7、5、3、2、1

現在讓我們討論獲得所需結果的方法 -

方法 1

這是一種簡單的方法，我們只需要從 0 到 n-1 迭代一個迴圈，對於每次迭代，我們都會找到長度最短的繩索，並從所有其他繩索中減去該長度，現在我們將計算所有剩餘長度不為零的繩索，並輸出此類繩索的數量。我們將繼續執行此過程，直到沒有繩索剩餘。

這不是解決此問題的最佳實踐，因為處理所需的時間過長。

示例

此方法的程式碼如下所示 -

#include <bits/stdc++.h>
using namespace std;
int main () {
   int rps [] = { 5, 1, 6, 9, 8, 11, 2, 2, 6, 5 } ;
   int nums = 10 ;
   cout << " The ropes left after each cut operation is" << endl;
   while (true) {        
      int min_rope = INT_MAX;
      for (int iterator = 0 ; iterator  < nums  ; iterator++){
         if (rps[iterator] > 0) {
            min_rope = min(min_rope, rps[iterator]);
         }
      }
      if (min_rope == INT_MAX) {
         break;
      }
      int c = 0;
      for (int iterator = 0 ; iterator < nums ; iterator++) {
         if (rps[iterator] > 0) {
            rps[iterator] -= min_rope;
            if (rps[iterator] > 0) {
               c++ ;
            }
         }
      }
      if(c>0){
         cout << c << endl;
      }
   }
   return 0;
}

輸出

The ropes left after each cut operation is
9
7
5
3
2
1

• 時間複雜度 - 由於我們使用了巢狀迴圈，因此此方法的時間複雜度為 O(N^2)。

• 空間複雜度 - 由於在此方法中未使用額外的空間，因此空間複雜度為 O(1)。

方法 2

在此方法中，我們將首先對陣列進行排序，然後迭代排序後的陣列，每次刪除最短的繩索，並在每次迭代後計算剩餘的繩索數量。

此方法的步驟如下所示 -

• 對最初包含每條繩索長度的給定陣列進行排序

• 最初，要剪掉的長度將為 rps[0]

• 現在迭代陣列，如果 (rps[i] - 要剪掉的長度 > 0)

• 如果上述條件為真，即如果排序陣列中當前繩索的長度大於零，則當前繩索右側的繩索長度也將大於零。

• 因此，我們只需要列印剩餘的繩索數量，即 (nums - 迭代器)，即當前繩索右側存在的繩索數量。

• 現在要剪掉的下一個長度將為長度 rps[i]

• 對所有繩索重複相同的過程。

示例

此方法的程式碼解決方案如下所示。

#include <bits/stdc++.h>
using namespace std;
void rpscutting(int rps[], int nums){
   cout<< " The length of ropes left after each cutting operations is " << endl;
   sort(rps, rps + nums);
   int opr = 0;
   int lencut = rps[0];
   for (int iterator = 1; iterator < nums; iterator++){		
      if ( rps[iterator] - lencut > 0){
         cout << (nums - iterator) << " ";
         lencut = rps[iterator];
         opr++;
      }
   }
   if (opr == 0)
      cout << "0 ";
}
int main(){
   int rps[] = { 5, 1, 6, 9, 8, 11, 2, 2, 6, 5 } ;
   int nums = sizeof(rps) / sizeof(rps[0]) ;
   rpscutting(rps, nums) ;
   return 0;
}

輸出

The length of ropes left after each cutting operations is 
9 7 5 3 2 1

• 時間複雜度 - 此方法的時間複雜度為 O(nlogn)。

• 空間複雜度 - 由於未使用額外的空間，因此空間複雜度為 O(1)。

結論

我們討論了兩種不同的方法來解決“每次移除最短繩索後剩餘的繩索”問題。最初的時間複雜度，即第一種方法的時間複雜度為 O(n^2)，我們在後一種方法中將其降低到 O(nlogn)。