【排列距离 / B】

康托展开详解_康托展开原理-CSDN博客

题目

TLE代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int cntall = 1, m1, m2;string s = "abcdefghijklnopqr";while (next_permutation(s.begin(), s.end())){if (s == "aejcldbhpiogfqnkr")m1 = cntall;else if (s == "ncfjboqiealhkrpgd")m2 = cntall;cntall++;}cout << min(abs(m2 - m1), cntall - abs(m2 - m1));
}

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a1, a2;
LL f[20];
void get_f(int n)
{f[1] = 1;for (int i = 2; i <= n; i++){f[i] = i * f[i - 1];}
}
void canto(string str, LL &x)
{int n = str.size();for (int i = 0; i < n; i++){int temp = 0;for (int j = i + 1; j < n; j++){if (str[i] > str[j])temp++;}x += temp * f[n - 1 - i];}
}
int main()
{get_f(17);string s1 = "aejcldbhpiogfqnkr";string s2 = "ncfjboqiealhkrpgd";canto(s1, a1), canto(s2, a2);cout << min(abs(a1 - a2), f[17] - abs(a1 - a2));
}