Đề bài
Cho một mảng N phần tử và một số nguyên K. Cho phép thực hiện phép toán sau bất kỳ số lần nào trên mảng cho trước:
- Chèn phần tử thứ K vào cuối mảng và xóa phần tử đầu tiên của mảng.
Nhiệm vụ là tìm số lần di chuyển tối thiểu cần thiết để làm cho tất cả các phần tử của mảng bằng nhau. In -1 nếu không thể.
Nếu arr[] = {1, 2, 3, 4, 5, 6} và k = 6 thì tối thiểu 5 lần di chuyển: Move-1: {2, 3, 4, 5, 6, 6} Move-2: {3, 4, 5, 6, 6, 6} Move-3: {4, 5, 6, 6, 6, 6} Move-4: {5, 6, 6, 6, 6, 6} Move-5: {6, 6, 6, 6, 6, 6}
Thuật toán
1. Trước tiên chúng ta sao chép a[k] vào cuối, rồi a[k+1] và cứ thế 2. Để đảm bảo chúng ta chỉ sao chép các phần tử bằng nhau, tất cả các phần tử trong khoảng K đến N phải bằng nhau. Chúng ta cần loại bỏ tất cả các phần tử trong khoảng 1 đến K không bằng a[k] 3. Tiếp tục áp dụng các phép toán cho đến khi đến phần tử bên phải nhất trong khoảng 1 đến K không bằng a[k].
Ví dụ
#include <iostream> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int getMinMoves(int *arr, int n, int k){ int i; for (i = k - 1; i < n; ++i) { if (arr[i] != arr[k - 1]) { return -1; } } for (i = k - 1; i >= 0; --i) { if (arr[i] != arr[k - 1]) { return i + 1; } } return 0; } int main(){ int arr[] = {1, 2, 3, 4, 5, 6}; int k = 6; cout << "Minimum moves required = " << getMinMoves(arr, SIZE(arr), k) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum moves required = 5