BOJ 14458 - 소가 길을 건너간 이유 10
Inversion Counting을 계속 원소들을 교체해가면서 세주는 문제이다.
여기서 처음 배열의 Inversion Counting을 세준다음에, 생각해보자.
제일 뒤의 원소를 제일 앞으로 보내는 연산은 다음과 같이 개수에 영향을 미친다.
가 로 가야할 때, 개 만큼 개수가 줄어든다.
왜냐면 가 현재 가장 제일 마지막 원소이기 때문에 그것과 교차하는 것은 개의 오른쪽에 있는 원소들의 개수이기 때문이다.
또, 만큼 교차하는 것의 개수가 늘어난다.
가장 앞으로 가면 그것과 교차하는 것의 개수는 개 가 증가하기 때문이다.
그러므로 이 연산을 쭉 해주면 된다.
주의할건, 처음 배열이 가 주어졌을 때, 에서도 정답을 구해보고 에서도 정답을 구해봐야 한다는 것이다.
struct fenwick {
vi tree;
int n;
fenwick(int n) : n(n), tree(vi(n + 1)) {}
void update(int i, int v) {
i++;
while (i <= n) {
tree[i] += v;
i += i & -i;
}
}
int sum(int i) {
i++;
int ret = 0;
while (i) {
ret += tree[i];
i -= i & -i;
}
return ret;
}
};
void solve() {
int n;
cin >> n;
vi a(n), c(n);
fv(a);
fv(c);
for (int &i: a) i--;
for (int &i: c) i--;
int A = 2e15;
for (int it = 0; it < 2; it++) {
auto b = c;
vi idx(n), to(n);
for (int i = 0; i < n; i++) idx[a[i]] = i;
for (int i = 0; i < n; i++) b[i] = idx[b[i]];
for (int i = 0; i < n; i++) to[b[i]] = i;
fenwick fenw(n);
ll inv = 0;
for (int i = n - 1; i >= 0; i--) {
inv += fenw.sum(to[i]);
fenw.update(to[i], 1);
}
ll ans = inv;
for (int i = n - 1; i >= 0; i--) {
inv += b[i] * 2ll - n + 1;
ans = min(ans, inv);
}
A = min(A, ans);
swap(a, c);
}
cout << A;
}
Comments