OI题库

【题目描述】

排序是生活中最常见的操作之一，计算机科学对此大有用武之地。稍有常识的人都知道，基于交换的排序时间复杂度下界是O(nlogn)。这意味着可能设计出的最好排序算法将用至少O(nlog(n))次交换操作来给n个整数排序。虽然如此，对给定的n个整数，如果你知道每个数在排序后的位置，那么你总能找到一个包含至多n-1次交换的操作序列来将它们按升序排列。考虑四个元素<1 2 3 4>，有24种可能的排列，并且你知道每个元素在排序后的位置。

如果排列是<2 1 4 3>，至少需要进行2次交换来让它有序（分别交换1,2和4,3）。如果排列是<2 3 4 1>，就至少需要进行3次交换。<4 2 3 1>需要1次交换，<1 2 3 4>不需要交换。用这种方法，我们可以找到包含N个不同整数，并且至少交换K次才能排序的排列数。

【输入格式】

输入包含最多250组数据。

每组数据占1行，含2个正整数N(1<=N<=21)和K(0<=K<N)。

输入结束标志为N=K=0.

【输出格式】

对于每组数据，输出至少交换K次才能排序的排列数。

【样例输入】

3 1
3 0
3 2
0 0

【样例输出】

3
1
2

【来源】

UVa11077 Find the Permutations

刘汝佳，《算法竞赛入门经典训练指南》表2-10

Problemsetter: Md. Kamruzzaman

Special Thanks: Abdullah-al-Mahmud