Mô tả
Cho một dãy N số có hoán vị của N số đầu tiên. Trong một thao tác duy nhất, bất kỳ tiền tố nào cũng có thể được đảo ngược. Nhiệm vụ là tìm số lượng tối thiểu các phép toán như vậy sao cho các số trong mảng được sắp xếp theo thứ tự tăng dần.
Ví dụ
Nếu mảng là {1, 2, 4, 3} thì cần tối thiểu 3 bước để sắp xếp mảng theo thứ tự tăng dần -
- Đảo ngược toàn bộ mảng {3, 4, 2, 1}
- Đảo ngược hai phần tử đầu tiên {4, 3, 2, 1}
- Đảo ngược toàn bộ mảng {1, 2, 3, 4}
Thuật toán
- Mã hóa các số đã cho trong một chuỗi. Sắp xếp mảng và mã hóa nó thành một chuỗi đích.
- Sau đó, thực hiện một BFS từ hoán vị ban đầu. Mỗi lần, hãy kiểm tra tất cả các hoán vị được tạo ra bằng cách đảo ngược tiền tố của hoán vị hiện tại.
- Nếu nó không được truy cập, hãy đưa nó vào hàng đợi với số lần đảo ngược được thực hiện.
- Khi hoán vị của chuỗi được mã hóa giống với chuỗi đích, hãy trả về số lần đảo ngược bắt buộc để đạt được tại đây
- Nghĩa là, tất cả các hoán vị của các chuỗi đều được thực hiện và giá trị nhỏ nhất trong số đó được trả về dưới dạng câu trả lời.
Ví dụ
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int minimumPrefixReversals(int *a, int n) {
string start = "";
string destination = "", t, r;
for (int i = 0; i < n; i++) {
start += to_string(a[i]);
}
sort(a, a + n);
for (int i = 0; i < n; i++) { destination += to_string(a[i]);
}
queue<pair<string, int> > qu;
pair<string, int> p;
qu.push(make_pair(start, 0));
if (start == destination) {
return 0;
}
while (!qu.empty()) {
p = qu.front();
t = p.first;
qu.pop();
for (int j = 2; j <= n; j++) {
r = t;
reverse(r.begin(), r.begin() + j);
if (r == destination) {
return p.second + 1;
}
qu.push(make_pair(r, p.second + 1));
}
}
}
int main() {
int a[] = { 1, 2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << "Minimum reversal: " << minimumPrefixReversals(a, n) << 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 reversal: 3