ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด N และค่าจำนวนเต็ม M ภารกิจของเราคือ หาตำแหน่งขององค์ประกอบที่ถูกลบออกสุดท้ายจากอาร์เรย์
การลบค่าจากอาร์เรย์ขึ้นอยู่กับการดำเนินการ -
- สำหรับองค์ประกอบในอาร์เรย์ arr[i] ถ้า arr[i] > M ให้เอาค่าออกและนำ arr[i] - M ไปไว้ท้ายอาร์เรย์ มิฉะนั้นให้ลบออกจากอาร์เรย์
ดำเนินการต่อจนกว่าอาร์เรย์จะประกอบด้วยองค์ประกอบ
มาดูตัวอย่างเพื่อเข้าใจปัญหา
อินพุต
arr[] = {5, 4, 8}, M = 3
เอาต์พุต
3
คำอธิบาย
การลบค่าโดยใช้การดำเนินการ {5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} -> empty array. ค่าที่ถูกลบออกสุดท้ายคือ 8 ตำแหน่งคือ 3
วิธีการแก้ปัญหา
วิธีแก้ปัญหาแบบง่ายคือการหาค่าที่ถูกลบออกสุดท้ายโดยใช้ข้อเท็จจริงว่าค่าแต่ละค่าที่จะถูกลบออกสุดท้ายมีค่า ceil(arr[i] / M) มากที่สุด
เพื่อหาตำแหน่งขององค์ประกอบที่ออกจากอาร์เรย์สุดท้าย เราจะเดินทางผ่านอาร์เรย์และเก็บตำแหน่งที่มีค่าสูงสุดของ ceil(arr[i] / M)
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <iostream> using namespace std; int findLastRemPos(int arr[], int n, int m){ for (int i = 0; i < n; i++) { arr[i] = (arr[i] / m + (arr[i] % m != 0)); } int lastRemPos = -1, largestVal = -1; for (int i = n - 1; i >= 0; i--) { if (largestVal < arr[i]) { largestVal = arr[i]; lastRemPos = i; } } return lastRemPos + 1; } int main(){ int arr[] = {5, 4, 8, 1}; int n = sizeof(arr) / sizeof(arr[0]); int m = 3; cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m); return 0; }
เอาต์พุต
The position of last removed element in the array is 3
