Joh*_*ith 7 algorithm math permutation
最近我开始解决在线评委的问题.我在SPOJ中遇到了这个问题:
这是一个改组N卡的算法:
- 卡被分成K个相等的桩,其中K是N的因子.
- 底部N/K卡以相同的顺序属于桩1(因此.initial桩的底部卡是桩1的底部卡).
- 底部的下一张N/K卡属于桩2,依此类推.
- 现在洗牌堆的顶牌是堆1的顶牌.下一张牌是堆2的顶牌,......,洗牌堆的Kth牌是堆K的顶牌.然后(K + 1)卡是现在位于桩1顶部的卡,(K + 2)nd是现在位于桩2顶部的卡,依此类推.
例如,如果N = 6且K = 3,则在洗牌一次时牌组"ABCDEF"(从上到下)的顺序将变为"ECAFDB".
给定N和K,在将桩恢复到原始顺序之后所需的最小洗牌次数是多少？
我试过模拟,但它超过了时间限制.有没有数学方程式？
是的，这个问题有一个数学解决方案。
首先让我从一些关于如何解决此类问题的提示开始，然后我将给出一些关于实际解决方案的提示。我不会完全完成它，因此仍然存在一些挑战。
那么：如何处理此类问题呢？你所做的实际上是一个好的开始。编写一个模拟并针对一些小案例运行它。那里的模拟应该相当快。现在你有了更多的价值观。将它们写在一张纸上并开始盯着它们看。例如，如果 K = x 1且 N = y 1，则结果是 z 1以及更多这样的对。尝试找出一些公式。重点关注 x、y 或 z 具有固定值的三元组。他们有什么共同点？等等。你盯着看，通常在一段时间后你会得到一个好主意:)
现在：关于这个特定问题的一些提示。进行一次洗牌迭代并记下每张牌的去向。例如，卡 1 位于位置 3，卡 3 位于位置 2，依此类推。请注意，某些链将以这种方式形成 - 例如在示例中 n=6，k=3，我们有一个长度为 6 的链： 1->3->2->6->4->5->1 。现在计算所有链的长度（每张卡都属于一个链）并尝试找出答案如何取决于这些长度。
希望这足以帮助您解决问题。
编辑：看看模拟单次迭代的约束可能会非常慢。如果是这种情况，在完成我在第二个技巧中建议的操作后，尝试计算链的长度，而无需实际模拟一次洗牌