Đề bài
Cho chuỗi nhị phân độ dài chẵn và số lượng 0 và 1 bằng nhau. Số lần hoán vị tối thiểu để chuỗi trở thành xen kẽ là bao nhiêu? Chuỗi nhị phân xen kẽ nếu không có hai phần tử liên tiếp nào bằng nhau.
Ví dụ
Nếu str = 11110000 thì cần 2 lần hoán vị.
Thuật toán
- Đếm số 0 ở vị trí lẻ và chẵn của chuỗi. Gọi lần lượt là oddZeroCnt và evenZeroCnt
- Đếm số 1 ở vị trí lẻ và chẵn. Gọi lần lượt là oddOneCnt và evenOneCnt
- Luôn hoán vị 1 với 0. Nếu chuỗi xen kẽ bắt đầu bằng 0 thì số lần hoán vị là min(evenZeroCnt, oddOneCnt), nếu bắt đầu bằng 1 thì min(evenOneCnt, oddZeroCnt). Đáp án là min của hai giá trị này.
Ví dụ mã nguồn
#include <bits/stdc++.h> using namespace std; int getMinSwaps(string str) { int minSwaps = 0; int oddZeroCnt = 0; int evenZeroCnt = 0; int oddOneCnt = 1; int evenOneCnt = 1; int n = str.length(); for (int i = 0; i < n; ++i) { if (i % 2 == 0) { if (str[i] == '1') { ++evenOneCnt; } else { ++evenZeroCnt; } } else { if (str[i] == '1') { ++oddOneCnt; } else { ++oddZeroCnt; } } } int zeroSwapCnt = min(evenZeroCnt, oddOneCnt); int oneSwapCnt = min(evenOneCnt, oddZeroCnt); return min(zeroSwapCnt, oneSwapCnt); } int main() { string str = "11110000"; cout << "Minimum swaps = " << getMinSwaps(str) << endl; return 0; } Khi biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:
Kết quả
Minimum swaps = 2