ข้อกำหนดโจทย์
กำหนดจำนวนเต็ม 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. เรียงลำดับองค์ประกอบที่กำหนด 2. ใช้ greedy approach วิธีที่ดีที่สุดคือลบองค์ประกอบต่ำสุดหรือสูงสุด แล้วตรวจสอบว่า Amax - Amin <= K มีรูปแบบการลบต่างๆ ที่ต้องพิจารณา 3. จะมีสองวิธีการลบที่เป็นไปได้ คือ เราลบค่าต่ำสุด หรือเราลบค่าสูงสุด ให้ (i...j) เป็นดัชนีขององค์ประกอบที่เหลือหลังการลบ เริ่มต้น i=0 และ j=n-1 และจำนวนองค์ประกอบที่ลบคือ 0 ตอนต้น 4. เราลบองค์ประกอบก็ต่อเมื่อ a[j]-a[i] > k สองวิธีการลบที่เป็นไปได้คือ (i+1...j) หรือ (i...j-1) นำค่าต่ำสุดของทั้งสองมาใช้
ตัวอย่างโค้ด 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 << "Minimum numbers to be removed = " << removeNumbers(arr, n, k) << endl;
return 0;
}
เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้
ผลลัพธ์
Minimum numbers to be removed = 5
