Chương trình tìm số lần hoán đổi tối thiểu cần thiết để sắp xếp tất cả các đôi vớ với nhau trong C ++

Giả sử chúng ta có một danh sách các số được gọi là hàng và đây là đại diện cho tất nằm trong một hàng. Chúng không được sắp xếp, nhưng chúng tôi muốn sắp xếp lại chúng để mỗi đôi tất nằm cạnh nhau như (0, 1), (2, 3), (4, 5), v.v. Chúng tôi phải tìm số lượng hoán đổi tối thiểu cần thiết để sắp xếp lại chúng.

Vì vậy, nếu đầu vào giống như row =[0, 5, 6, 2, 1, 3, 7, 4], thì đầu ra sẽ là 2, vì thứ tự hàng là

• [0, 5, 6, 2, 1, 3, 7, 4]

• [0, 1, 6, 2, 5, 3, 7, 4]

• [0, 1, 3, 2, 5, 6, 7, 4]

• [0, 1, 3, 2, 5, 4, 7, 6]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng p và một mảng sz khác

• Xác định một hàm find (), điều này sẽ lấy u,

• return (nếu p [u] giống với u thì u, nếu không thì find (p [u]) và p [u]:=find (p [u]))

• Xác định một hàm tham gia (), điều này sẽ lấy u, v,

• pu:=find ((u), pv:=find (v))

• nếu pu giống với pv thì -

  • trở lại

• nếu sz [pu]> =sz [pv], thì -

  • p [pv]:=pu

  • sz [pu]:=sz [pu] + sz [pv]

• Nếu không

  • p [pu]:=pv

  • sz [pv]:=sz [pv] + sz [pu]

• Từ phương thức chính, thực hiện như sau -

• n:=kích thước của arr

• p:=một mảng có kích thước n

• để khởi tạo i:=0, khi i

  • p [i]:=i

• sz:=một mảng có kích thước n và điền bằng 1

• để khởi tạo i:=0, khi i

  • u:=arr [i / 2] / 2

  • v:=arr [(i / 2) HOẶC 1] / 2

  • tham gia (u, v)

• ans:=0

• để khởi tạo i:=0, khi i

  • nếu find (i) giống với i, thì -

    • ans:=ans + sz [i] - 1

  • trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;
int find(int u) {
   return p[u] == u ? u : p[u] = find(p[u]);
}
void join(int u, int v) {
   int pu = find(u), pv = find(v);
   if (pu == pv)
   return;
   if (sz[pu] >= sz[pv]) {
      p[pv] = pu;
      sz[pu] += sz[pv];
   }else {
      p[pu] = pv;
      sz[pv] += sz[pu];
   }
}
int solve(vector<int>& arr) {
   int n = arr.size() / 2;
   p = vector<int>(n);
   for (int i = 0; i < n; ++i)
   p[i] = i;
   sz = vector<int>(n, 1);
   for (int i = 0; i < n; ++i) {
      int u = arr[i << 1] / 2;
      int v = arr[i << 1 | 1] / 2;
      join(u, v);
   }
   int ans = 0;
   for (int i = 0; i < n; ++i)
   if (find(i) == i)
   ans += sz[i] − 1;
   return ans;
}
int main(){
   vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
   cout << solve(v);
}

Đầu vào

{2, 4, 6, 3}

Đầu ra

23