Số lần xóa từ mảng để max – min <= K trong C++

Đề bài

Cho N số nguyên và K, tìm số lượng phần tử tối thiểu cần xóa sao cho Amax - Amin <= K. Sau khi xóa, Amax và Amin được xem xét trong 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 là 5:

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

Thuật toán

1. Sắp xếp các phần tử cho trước.
2. Dùng tham lam, cách tốt nhất là xóa phần tử nhỏ nhất hoặc lớn nhất rồi kiểm tra Amax - Amin <= K. Có nhiều tổ hợp xóa cần xem xét.
3. Có 2 cách xóa có thể: xóa min hoặc xóa max. Cho (i...j) là chỉ số phần tử còn lại sau xóa. Ban đầu i=0, j=n-1, số phần tử xóa = 0.
4. Chỉ xóa phần tử nếu a[j]-a[i]>k, hai cách xóa là (i+1...j) hoặc (i...j-1). Lấy min của hai cách.

Ví dụ mã C++

#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 << "Số lượng số cần xóa tối thiểu = " << removeNumbers(arr, n, k) << endl;
    return 0;
}

Khi biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra sau

Đầu ra

Số lượng số cần xóa tối thiểu = 5