C++에서 max – min <=K를 만들기 위해 배열에서 최소 제거

문제 설명

N개의 정수와 K가 주어지면 Amax - Amin <=K가 되도록 제거해야 하는 요소의 최소 개수를 찾습니다. 요소를 제거한 후 나머지 요소 중 Amax와 Amin을 고려합니다.

예시

arr[] ={1, 3, 4, 9, 10, 11, 12, 17, 20}이고 k =4이면 출력은 5:

• 배열 시작 부분에서 1, 3, 4 제거
• 배열 끝에서 17과 20 제거
• 최종 배열은 {9, 10, 11, 12}가 됩니다. 여기서 12 – 9 <=4

알고리즘

1. Sort the given elements
2. Using greedy approach, the best way is to remove the minimum element or the maximum element and then check if Amax - Amin <= K. There are various combinations of removals that have to be considered.
3. There will be two possible ways of removal, either we remove the minimum or we remove the maximum. Let(i…j) be the index of elements left after removal of elements. Initially, we start with i=0 and j=n-1 and the number of elements removed is 0 at the beginnings.
4. We only remove an element if a[j]-a[i]>k, the two possible ways of removal are (i+1…j) or (i…j-1). The minimum of the two is considered

예시

#include <bits/stdc++.h>
#define MAX 100
using namespace std;
int dp[MAX][MAX];
int removeCombinations(int *arr, int i, int j, int k) {
   if (i >= j) {
   return 0;
   } else if ((arr[j] - arr[i]) <= k) {
      return 0;
   } else if (dp[i][j] != -1) {
      return dp[i][j];
   } else if ((arr[j] - arr[i]) > k) {
      dp[i][j] = 1 + min(removeCombinations(arr, i +
      1, j, k),
      removeCombinations(arr, i, j - 1,k));
   }
   return dp[i][j];
}
int removeNumbers(int *arr, int n, int k){
   sort(arr, arr + n);
   memset(dp, -1, sizeof(dp));
   return n == 1 ? 0 : removeCombinations(arr, 0, n - 1,k);
}
int main() {
   int arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 4;
   cout << "Minimum numbers to be removed = " <<
   removeNumbers(arr, n, k) << endl;
   return 0;
}

위의 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다.

출력

Minimum numbers to be removed = 5