首页 > 代码库 > 组合题目的分析

组合题目的分析




               首先不妨考虑1个特殊情况,当n趋于无穷的时候,|t| = 1, 显然可以。

             

               然后考虑任意一个长度为2*n的区间。不妨设为[a, a + 2n] , 考虑该区间的任意

               一个整数m, 显然m = (a + n) + r, 其中r属于[-n, n]。故包含在该区间的ai都可以

               写成ai = t + s, 其中t  = (a + n).


                现在考虑对a1 , a2, ..., am分段

                [a1, a1 + 2n], [a(m),  a(m) + 2n], [a(t), a(t) + 2n]

                一共t个区间。则an属于最后一个区间

                am - a1 >= (2n + 1) * (t  - 1)

                所以t <= (am-a1)/(2n + 1) + 1


                故构造的集合满足条件。



组合题目的分析