最近我开始解决在线评委的问题.我在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,在将桩恢复到原始顺序之后所需的最小洗牌次数是多少？
我试过模拟,但它超过了时间限制.有没有数学方程式？
我最近做了一个测试...问题是长篇大论,解决方案归结为F(n)= 2*F(n-1)+ 2*F(n-2)......
我有一个使用动态编程的O(n)解决方案......但是,考官不满意......
我的解决方案是在计算时将每个F(n)存储在一个数组中.花了O(n)时间.因为我们只需要前两个元素,通过仅使用两个变量,就可以解决空间问题.
但是O(n)还不够快......
该函数看起来像斐波纳契函数,并且可以在O(lg n)时间内生成斐波纳契数...但是我无法获得O(lg n)soln来解决我的问题.
所以我的问题是如何改善功能的时间复杂度？