ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด N และค่าจำนวนเต็ม M หน้าที่ของเราคือ ค้นหาตำแหน่งขององค์ประกอบที่ถูกลบล่าสุดจากอาร์เรย์ .
การลบค่าออกจากอาร์เรย์จะขึ้นอยู่กับการดำเนินการ -
- สำหรับองค์ประกอบในอาร์เรย์ arr[i]. ถ้า arr[i]> M ให้เปิดค่าและกด arr[i] - M ไปที่ส่วนท้ายของอาร์เรย์ มิฉะนั้นให้ลบออกจากอาร์เรย์
ดำเนินการจนกว่าอาร์เรย์จะประกอบด้วยองค์ประกอบ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
arr[] = {5, 4, 8}, M = 3 ผลผลิต
3
คำอธิบาย
Removing values using operations,
{5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} ->
empty array.
The last value removed is 8, position is 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
