home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

การลบขั้นต่ำจากอาร์เรย์เพื่อให้สูงสุด – min <=K ใน C++

คำชี้แจงปัญหา

กำหนดจำนวนเต็ม 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 โดยใช้วิธีการโลภ วิธีที่ดีที่สุดคือลบองค์ประกอบขั้นต่ำหรือองค์ประกอบสูงสุดแล้วตรวจสอบว่า Amax - Amin <=K มีการผสมกันหลายอย่างที่ต้องพิจารณา3. การลบจะมีสองวิธีที่เป็นไปได้ เราลบค่าต่ำสุดหรือลบสูงสุด ให้(i…j) เป็นดัชนีขององค์ประกอบที่เหลือหลังจากลบองค์ประกอบ เริ่มแรก เราเริ่มต้นด้วย i=0 และ j=n-1 และจำนวนองค์ประกอบที่ถูกลบออกคือ 0 ที่จุดเริ่มต้น4. เราจะลบองค์ประกอบก็ต่อเมื่อ a[j]-a[i]>k การลบออกได้สองวิธีคือ (i+1…j) หรือ (i…j-1) ถือว่าขั้นต่ำของทั้งสอง

ตัวอย่าง

#include #define MAX 100 โดยใช้เนมสเปซ std;int dp[MAX][MAX];int removeCombinations(int *arr, int i, int j, int k) { if (i>=j) { กลับ 0; } else if ((arr[j] - arr[i]) <=k) { return 0; } อื่น ๆ if (dp[i][j] !=-1) { return dp[i][j]; } อื่น if ((arr[j] - arr[i])> k) { dp[i][j] =1 + min(removeCombinations(arr, i + 1, j, k), removeCombinations(arr, i, เจ - 1,k)); } ส่งคืน dp[i][j];}int removeNumbers(int *arr, int n, int k){ sort(arr, arr + n); memset(dp, -1, sizeof(dp)); ส่งคืน 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 <<"จำนวนขั้นต่ำที่จะลบ =" < 

 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ดังต่อไปนี้
 
ผลลัพธ์
 
จำนวนขั้นต่ำที่จะลบ =5