1. 길이가 x인 수열을 한 번 이상의 연산을 수행했을 때, 정렬 결과로 나올 수 있는 경우의 수는 x!이다.
2. 내부에서 연산을 수행하는 속도는 약 O(x)다. 따라서 1.의 결과로 보면 속도는 최대 8!*8이다.
3. 하지만 이를 들어오는 쿼리마다 수행할 수는 없으므로 "미리" 저장을 해놓고 들어오는 입력에 따라 O(C lg(x!*x)) 시간으로 찾을 수 있도록 한다.
4. 최대가 8이므로 길이 8짜리만 구하고, 나머지 길이에 대해서는 남는 부분을 오름차순으로 채우고 찾으면 된다.
- 코드
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
int main() {
int C, N, D, cnt, i, j, k, cur = 0, sz, u, v, pow10[10] = { 1 }, t = 0, a, b;
for (i = 1; i < 10; i++) pow10[i] = pow10[i - 1] * 10;
queue<int> q;
map<int, int> vi;
for (i = 1; i <= 8; i++) {
t *= 10;
t += i;
}
q.push(t);
vi[t] = 0;
while (!q.empty()) {
sz = q.size();
cur++;
while (sz--) {
u = q.front(), q.pop();
for (i = 0; i < 8; i++) {
for (j = i + 1; j < 8; j++) {
v = u;
for (k = 0; k < (j - i + 1) / 2; k++) {
a = (v / pow10[i+k]) % 10;
b = (v / pow10[j-k]) % 10;
v -= a * pow10[i+k] + b * pow10[j-k];
v += b * pow10[i+k] + a * pow10[j-k];
}
if (vi.count(v) == 0) {
vi[v] = cur;
q.push(v);
}
}
}
}
}
vector<int> sorted(8);
scanf("%d", &C);
while (C--) {
scanf("%d", &N);
vector<int> vt, origin;
for (i = 0, cnt = 1; i < N; i++, cnt++) {
scanf("%d", &D);
vt.push_back(D);
}
for(i=0;i<8;i++) sorted[i] = i + 1;
origin = vt;
sort(vt.begin(), vt.end());
for (i = 0; i < N; i++) for (j = 0; j < N; j++) {
if (origin[i] == vt[j]) {
sorted[i] = j + 1;
break;
}
}
u = 0;
for (int& s : sorted) {
u *= 10;
u += s;
}
printf("%d\n", vi[u]);
}
return 0;
}