Loại bỏ tối đa khỏi mảng khi thời gian xóa> =thời gian chờ trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng gồm N phần tử. Nhiệm vụ của chúng tôi là tìm mức xóa tối đa khỏi mảng khi thời gian xóa> =thời gian chờ.

Vì vậy, ở đây chúng ta sẽ loại bỏ các phần tử của mảng. Giá trị của phần tử của mảng biểu thị thời gian xóa (thời gian cần thiết để xóa phần tử khỏi mảng).

Phần tử có thời gian chờ là thời gian nó sẽ phải đợi cho đến khi được xóa.

Chỉ có thể xóa phần tử khỏi phần tử nếu thời gian xóa lớn hơn thời gian nó phải đợi.

Chúng ta phải tìm số phần tử tối đa có thể bị xóa khỏi mảng. Thứ tự của các phần tử trong mảng có thể được thay đổi theo yêu cầu.

hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={12, 3, 11, 7, 5}

Đầu ra - 2

Giải thích -

Đầu tiên, chúng tôi sẽ sắp xếp lại mảng theo thứ tự tăng dần -

Mảng sẽ là {3, 5, 7,11, 12}

Bây giờ, chúng tôi sẽ xóa từng phần tử một

Xóa 3 - thời gian chờ là 0 nhỏ hơn thời gian loại bỏ (3). Có thể loại bỏ.

Xóa 5 - thời gian chờ là 3 nhỏ hơn thời gian gỡ bỏ (5). Có thể loại bỏ.

Xóa 7 - thời gian chờ là 8 lớn hơn thời gian loại bỏ (7). Không thể xóa.

Để giải quyết vấn đề này, chúng tôi sẽ sắp xếp và kiểm tra từng phần tử cần loại bỏ.

Thuật toán

Step 1: Sort the array in ascending order.
Step 2: For every element in the array, Do:
Step 3: Find waiting Time (sum of removal time of all elements before the element).
Step 4: if (waiting time <= removal time )
   step 4.1: remove the element and increase the remove count.
Step 5: else: break.
Step 6: print the number of elements removed.

Ví dụ

Chương trình tìm giá trị Loại bỏ tối đa khỏi mảng khi loại bỏ thời gian> =thời gian chờ trong C ++

#include <bits/stdc++.h>
using namespace std;
int countRemovedElements(int arr[], int n){
   sort(arr, arr + n);
   int removeCount = 0;
   int waitTime = 0;
   for (int i = 0; i < n; i++) {
      if (arr[i] >= waitTime) {
         removeCount++;
         waitTime += arr[i];
      }
      else
         break;
   }
   return removeCount;
}
int main(){
   int arr[] = { 12, 3, 11, 7 , 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum number of elements that can be removed from the array is "<<countRemovedElements(arr, n);
   return 0;
}

Đầu ra

The maximum number of elements that can be removed from the array is 2