Anti-Fibonacci Permutation 题解
原题链接:Link
题目简介
简单来说,如果在一个序列 \(A\) 中,对于每一个 \(i > 2\) ,都有 \(A_i \ne A_{i-1}+A_{i-2}\) ,那么 \(A\) 被称为反斐波那契数列。就是不符合斐波那契数列要求的数列。题目要求构造出 \(n\) 个这样的数列,每一个数都要在 \(1 \sim n\) 之间。
构造思路
显然枚举全排列然后每次都 \(O(n)\) 判一遍是可行的,但是最好不要自己写全排列,容易 \(T\) 。建议使用 STL
的 next_permutation()
函数(用法可以百度)。可以知道这样的最坏复杂度是 \(O(n^2)\) 的,因为 next_permutation()
的复杂度最坏是 \(O(n)\) 。不过我们有更好的方法。
考虑序列 \(A=\{ n, n-1, n-2,...,2, 1 \}\) ,它一定是反斐波那契数列。因为 \(A_i\) 显然比 \(A_{n-1}\) 和 \(A_{n-2}\) 更小。然后我们考虑把最后一个数放到第一个,即 \(A'=\{1,n,n-1,...,3,2\}\) ,它也是一个反斐波那契数列,因为 \(n-1 < n+1\) ,然后构造 \(A''=\{2,1,n,n-1,...,4,3\}\) ,这里有一个小小的曲折:如果 \(n=2+1=3\) ,那么它就不是反斐波那契数列,但不用担心,特判 \(n=3\) 之后把样例输出就可以了。对于其他的 \(n\) , \(A''\) 显然也是反斐波那契数列。之后的构造就顺风顺水,重复把最后一个数放到第一个的操作,可以知道所得 \(n\) 个序列都是反斐波那契数列,就有答案了。证明如下:
对于构造的第 \(i\) 个数列,一定符合 \(i-1,i-2,i-3,...,2,1,n,n-1,...,i+1,i\) 的形式。由之前构造的 \(A\) 数列,可以知道递减序列一定是反斐波那契数列,那么只要 \(2,1,n,n-1\) 这一段两个递减序列接合的地方满足要求即可。又由 \(A''\) 的构造中知道,当 \(n>3\) 时,接合处也满足要求,所以第 \(i\) 个数列一定是反斐波那契数列。
时间复杂度 \(O(n)\) 。
AC代码
1 |
|