Tuyên bố vấn đề
Cho một mảng gồm N phần tử và một số nguyên K., được phép thực hiện phép toán sau với số lần bất kỳ trên mảng đã cho -
-
Chèn K th ở 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ể
If arr[] = {1, 2, 3, 4, 5, 6} and k = 6 then minimum 5 moves are
required:
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. First we copy a[k] to the end, then a[k+1] and so on 2. To make sure that we only copy equal elements, all elements in the range K to N should be equal. We need to remove all elements in range 1 to K that are not equal to a[k] 3. Keep applying operations until we reach the rightmost term in range 1 to K that is not equal to 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;
} Đầu ra
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