Để sắp xếp lại mảng sao cho những số cùng giá trị phải được đặt liên tiếp nhau, ta có thể sử dụng thuật toán Counting Sort như sau:

Đếm số lần xuất hiện của từng phần tử trong mảng.

Dựa vào số lần xuất hiện, xác định vị trí đầu tiên của từng phần tử trong mảng đã sắp xếp.

Sắp xếp lại mảng bằng cách chuyển từng phần tử đến vị trí tương ứng trong mảng đã sắp xếp.

Đếm số lần cần phải chuyển để sắp xếp mảng.

Dưới đây là mã giả của thuật toán:
 

int a[n];
int count[21] = {0}; // Khởi tạo mảng đếm

// Đếm số lần xuất hiện của từng phần tử trong mảng
for (int i = 0; i < n; i++) {
    count[a[i]]++;
}

// Xác định vị trí đầu tiên của từng phần tử trong mảng đã sắp xếp
int pos[21] = {0};
for (int i = 1; i <= 20; i++) {
    pos[i] = pos[i - 1] + count[i - 1];
}

// Sắp xếp lại mảng bằng cách chuyển từng phần tử đến vị trí tương ứng trong mảng đã sắp xếp
int b[n];
for (int i = 0; i < n; i++) {
    b[pos[a[i]]++] = a[i];
}

// Đếm số lần cần phải chuyển để sắp xếp mảng
int swaps = 0;
for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) {
        swaps++;
    }
}

cout << swaps << endl;

Độ phức tạp của thuật toán là O(n), với n là số lượng phần tử trong mảng.

Thông thường khi gặp một bài toán về số thao tác ít nhất nếu n nhỏ thì theo mình có thể sử dụng BFS để giải quyết, ở đây đề yêu cầu là n < 10^5 nên khả năng ta phải lập một công thức để đánh giá độ hoàn thiện của mảng và dùng A* giải quyết.

Tuy nhiên cũng có thể có một quy luật đơn giản nào đó sẽ khiến bài toán trở nên dễ dàng hơn, mình không giỏi tìm cái quy luật này lắm nên bạn tự suy nghĩ thử xem (không chắc là có nha). Sau thì mình đánh giá bài này là khó nên nếu ai đó ra đề thì chắc sẽ có bài giải thôi.