Đề bài đây ạ : Cho một mảng nhị phân V có kích thước 2 × N gồm N giá trị 0 và N giá trị 1 . Bạn có thể hoán đổi hai số bất kỳ trong mảng. Hỏi số hoán đổi ít nhất để biến mảng đã cho thành mảng đặc biệt là bao nhiêu? Biết rằng một mảng được coi là đặc biệt khi không có hai phần tử liên tiếp nào của mảng bằng nhau.
Input:
3
0 0 0 1 1 1
Output:
1
E bí lắm r :v . E rất mong được mọi người giúp đỡ ạ.
Bạn tạo 1 form chuẩn cho bài. VD: có 4 số 1 và 0(2 số 1 và 2 số 0) thì có 2 form thế này 0101 và 1010.
Bước kế tiếp sẽ dùng 1 form để so với form input vào. cứ mỗi cặp vị trí khác nhau là 1 hoán đổi.
VD form: 010101 và input 001110
010101
001110
kq: 4 vị trí khác nhau => 2 lần hoán đổi. Vị trí (2,3) và (5,6)
@Nguyen_Nam4 Thật ra chỉ cần hoán đổi một lần thôi, 1 đổi cho 4 sẽ thành : 101010
Cách của bạn phải tạo 2 form, một form từ 0 và một form từ 1 mới chắc hết các trường hợp 
@Do_Nam1 Cách của mình như sau: Chạy 1 vòng for để xét các số nằm cạnh nhau mà giống nhau, sau đó chia hai thì sẽ ra số lần cần đổi vị trí.
VD1: 0 0 0 1 1 1
Ở đây có hai cặp số nằm cạnh nhau và bằng nhau ==> Số lần cần phải chuyển là: 2 / 2 = 1.
VD2: 00 11 10
Ở đây cũng có 2 cặp số như vậy ==> Số lần cần phải chuyển là: 2 / 2 = 1.
Vẫn là một lần thôi :)) Đổi 2 cho 5 thì sẽ thành 101010
Cách của bạn ý phải tạo 2 form, một form từ 0 và một form từ 1 mới chắc hết các trường hợp
Bạn thử test với 0 0 1 1 1 0 1 0 0 1 nhé
@Do_Nam1
Cảm ơn bạn đã chỉ ra bug của thuật toán Sửa lại một chút thôi
Nếu như số cặp là số lẻ, tình số lần cẩn chuyển sẽ là: (số cặp / 2) + 1
Giải thích: Ở VD của bạn : 0 0 1 1 1 0 1 0 0 1 thì có 3 cặp số phù hợp, vậy nên ta cần phải chuyển vị trí 2 số để làm mất đi một cặp số, ở đây có thể là: vị trí thứ 5 và số 6 ==> Dãy trở thành: 0 0 1 1 1 0 1 0 1 0. Vậy là chỉ còn 2 cặp số thôi, chia hết cho 2 được rồi
==> Output: 2 lần (Đổi 5 với 6; 1 với 4)
P/s: Mình cũng vừa nghĩ ra cách khác, sử dụng cách ban đầu của bạn @Nguyen_Nam4. Khi tìm ra được số phần từ khác nhau rồi (Giả sử đó là n) .Nếu n <= size của mảng / 2 thì số lần phải đối = n / 2, còn nếu > hơn thì số lần phải đổi sẽ = (size - n) / 2. Tuy nhiên mình thấy cái này vẫn không tối ưu lắm, vì bạn phải tạo ra form mới nữa
Nếu bạn để ý số vị trí sai chia cho 2 sẽ ra số lần hoán thì bài sẽ đơn giản hơn nhiều.
Duyệt 1 vòng for là đúng rồi, để tìm được vị trí sai thì chỉ cần kiểm tra vị trí kế tiếp thôi. nếu giống nhau thì có thêm 1 vị trí sai và lúc này cập nhập lại vị trí đó sao cho đúng để khi tiếp tục vòng lọc bình thường.
Cũng na ná nhau thôi, không cái nào đơn giản hơn cả
Cách của bạn thì phải xử lý thêm một phần như mình nói ở trên
Còn cách của mình thì lại phải xử lý cả trường hợp nó là số lẻ nữa
Thực ra cũng không cần: (số cặp + 1)/2.
Cảm ơn bạn Giờ mới nhận ra
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?