USACO/cowcycle

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .3中的OI题目Cowcycles的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

搜索。题意不难理解，注释写得很清楚了。数据不是很BT，加些优化基本上就过了。 最大的数据不会出，放心做。按照从小到大的顺序扩展。

USACO总是把数据说的那么吓人，考验心理素质啊！

这道题同样算法用C++写比Pascal快得多。

优化技巧

• 最大传动比率至少是最小的3倍。这个其实不用算出比率再判断，只要不满足(s1[F]/s2[1]) / (s1[1]/s2[R])>=3的都剪掉 (s1表示前齿轮型号，s2表示后齿轮型号)。另外乘法计算要比除法快得多，上面判断式可以写成s1[F]*s2[R]>=3*s1[1]*s2 [1]。这个剪枝很有效果。
• 改变求方差的方法。
• 当找到比当前更优秀的解的时候，不要用For循环一个一个复制当前解，用memcpy函数会更快。
• 最想不到地地方，排序方法！开始我写成快排，一直过不了。其实数据的数量太少的时候，用快排效率很低的。在这里最适合的是简单插入排序。这个剪枝的效率很惊人！

就这些优化就可以通过了

求方差可以用期望来求

还有一个细节，答案中各个齿轮的大小各不相同，这个对防治TLE比较重要，虽然题里貌似没有说

开始先搜索前齿轮的极值，然后搜索后齿轮的极值，这样就有条件算最大最小传动比率，然后筛选有效极值，最后再在最大值最小值之间做普通搜索,因为不符合要求的状态都被提前排除了（I.e.普通搜索中间不符合要求的状态没必要搜），总搜索次数也减小了，这样效率会有显著提高。-----wearaway

参考代码

• C
• C++
• Pascal
• Java