행이라는 숫자 목록이 있고 이것이 행에 누워 있는 양말을 나타낸다고 가정합니다. 그것들은 정렬되어 있지 않지만 (0, 1), (2, 3), (4, 5) 등과 같이 각 양말 쌍이 나란히 있도록 재배열하고 싶습니다. 재정렬에 필요한 최소 스왑 수를 찾아야 합니다.
따라서 입력이 행 =[0, 5, 6, 2, 1, 3, 7, 4]와 같으면 행 순서가
이므로 출력은 2가 됩니다.-
[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]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
배열 p와 다른 배열 sz 정의
-
find() 함수를 정의하면 u가 필요합니다.
-
반환(p[u]가 u와 같으면 u, 그렇지 않으면 find(p[u]) 및 p[u] :=find(p[u]))
-
join() 함수를 정의하면 u, v,
가 필요합니다. -
pu :=찾기((u), pv :=찾기(v))
-
pu가 pv와 같으면 -
-
반환
-
-
sz[pu]>=sz[pv]이면 -
-
p[pv] :=푸
-
sz[pu] :=sz[pu] + sz[pv]
-
-
그렇지 않으면
-
p[pu] :=pv
-
sz[pv] :=sz[pv] + sz[pu]
-
-
주요 방법에서 다음을 수행하십시오 -
-
n :=arr의 크기
-
p :=n 크기의 배열
-
initialize i :=0의 경우, i
-
피[i] :=나
-
-
sz :=크기가 n이고 1로 채워진 배열
-
initialize i :=0의 경우, i
-
유 :=arr[i/2] / 2
-
v :=arr[(i/2) OR 1] / 2
-
조인(u,v)
-
-
답변 :=0
-
initialize i :=0의 경우, i
-
find(i)가 i와 같으면 -
-
ans :=ans + sz[i] − 1
-
-
반환
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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);
} 입력
{2, 4, 6, 3} 출력
23