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