USACO/frac1

来自NOCOW

[编辑] 分析

[编辑] 优化

1.0/1,1/x不能漏了！有1/1

2.若是两个偶数，不用判断绝对不行

3.两个分数比较大小，只需交叉相乘即可，无需另开data储存具体值。

 如：a1/b1<a2/b2 ==>a1*b2<a2*b1

[编辑] 快排

枚举所有的分数，判断其是否是最简（分母分子最大公约数＝1），用一个数列记录所有最简分数，然后用快排排序。

[编辑] 归并

显然，0/i 1/i 2/i...i/i这个序列是有序的对于n个序列归并即可（相等则取分母最小的一个——这样显然是最简分数）

[编辑] 数学

来自Russ的更优算法:

我们可以把0/1和1/1作为“端点”，通过把两个分数的分子相加、分母相加得到的新分数作为中点来递归（如图）

0/1                                                              1/1
                              1/2
                 1/3                      2/3
       1/4              2/5         3/5                 3/4
   1/5      2/7     3/8    3/7   4/7   5/8       5/7         4/5

每一个分数的分子和分母都是由求和得来的，这意味着我们可以通过判断和与N的大小关系来判断递归边界。

详细证明请参见http://blog.csdn.net/yuwuc/article/details/4540630 （该证明实际上摘自《具体数学》，没看懂的可以到这本书上找一下）

[编辑] hash

直接扫一遍，用hash自动把非最简分数筛掉

详见pascal代码11

[编辑] 枚举,利用STL

利用map的自动排序特性可以直接K.O.这题,把每个分数的大小算出来并转化成字符串,然后插入map.输出的时候直接遍历map就行了,时间复杂度O(n^2).代码见C++

[编辑] 另一种数学

由于任意两个分数的差一定>=1/（160*159），所以直接把所有分数乘上50880，四舍五入后直接桶排序，而且一边输入一边排，只需要同时记录分子分母就行了，O(n)！！。连化简都省了，遇到相同值就跳过（因为之前必定有一个数值更小的分数等于这个值）

[编辑] 纠正

其实由于输入数据是n的值，所有复杂度应该是O(10^(2n))

[编辑] 参考代码

C++
c
pascal
Java

[编辑] 引用

[1]

[2]