제거 시간>=C++에서 대기 시간일 때 배열에서 최대 제거

이 문제에서는 N 요소의 배열이 제공됩니다. 우리의 임무는 제거 시간>=대기 시간일 때 어레이에서 최대 제거를 찾는 것입니다.

그래서 여기서 우리는 배열의 요소를 제거할 것입니다. 배열 요소의 값은 제거 시간(배열에서 요소를 제거하는 데 걸리는 시간)을 나타냅니다.

요소에는 제거될 때까지 기다려야 하는 대기 시간이 있습니다.

제거 시간이 기다려야 하는 시간보다 긴 경우에서만 요소를 제거할 수 있습니다.

배열에서 제거할 수 있는 최대 요소 수를 찾아야 합니다. 배열의 요소 순서는 요구 사항에 따라 변경할 수 있습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력 - 배열 ={12, 3, 11, 7, 5}

출력 - 2

설명 -

먼저 배열을 오름차순으로 재정렬합니다 -

배열은 {3, 5, 7,11, 12}

이제 요소를 하나씩 제거하겠습니다.

3 제거 - 대기 시간은 제거 시간(3)보다 짧은 0입니다. 제거가 가능합니다.

5개 제거 - 대기 시간은 제거 시간(5)보다 짧은 3입니다. 제거가 가능합니다.

7 제거 - 대기 시간은 제거 시간(7)보다 긴 8입니다. 제거할 수 없습니다.

이 문제를 해결하기 위해 제거할 요소를 하나씩 정렬하고 확인합니다.

알고리즘

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.

예시

제거 시 배열에서 최대 제거를 찾는 프로그램>=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;
}

출력

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