每次移除最短绳索后剩余的绳索

---

在本文中，我们将讨论解决“每次移除最短绳索后剩余的绳索”问题的两种方法。

问题陈述

给定一个元素数组，其中 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)。