Số lần xóa tối thiểu khỏi mảng để tối đa - tối thiểu <=K trong C ++

Tuyên bố vấn đề

Cho N số nguyên và K, tìm số phần tử nhỏ nhất cần loại bỏ sao cho Amax - Amin <=K. Sau khi loại bỏ các phần tử, Amax và Amin được coi là trong số các phần tử còn lại

Ví dụ

Nếu arr [] ={1, 3, 4, 9, 10, 11, 12, 17, 20} và k =4 thì đầu ra sẽ là 5:

• Xóa 1, 3 và 4 khỏi đầu mảng
• Xóa 17 và 20 khỏi phần cuối của mảng
• Mảng cuối cùng trở thành {9, 10, 11, 12} trong đó 12 - 9 <=4

Thuật toán

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

Ví dụ

#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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau

Đầu ra

Minimum numbers to be removed = 5