Mô tả bài toán
Cho mảng và số M. Lặp: lấy phần tử đầu, nếu > M thì trừ M và đẩy về cuối, else xóa bỏ. Tìm vị trí ban đầu của phần tử bị xóa cuối cùng.
Ví dụ
arr={5,4,8}, M=3 → Output: 3 (phần tử 8 tại vị trí 3 bị xóa cuối).
Giải thuật
Phần tử bị xóa cuối cùng là phần tử có giá trị ceil(arr[i]/M) lớn nhất (nếu tie thì lấy vị trí sau cùng). Tính val[i] = (arr[i]+M-1)/M, tìm chỉ số lớn nhất có val max (duyệt ngược).
Mã nguồn C++
#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m) {
for (int i=0; i=0; i--)
if (maxVal < arr[i]) { maxVal = arr[i]; lastPos = i; }
return lastPos + 1; // 1-based
}
int main() {
int arr[] = {5,4,8,1};
int n = sizeof(arr)/sizeof(arr[0]);
int m = 3;
cout << "Position of last removed element: " << findLastRemPos(arr,n,m);
return 0;
} Đầu ra
Position of last removed element in the array is 3