可怜的奶牛

来自计算思维百科
跳转至: 导航搜索
可怜的奶牛.png

农夫有n头奶牛,可是由于他们产的奶太少,农夫对他们很不满意,决定每天把产奶最少的一头做成牛肉干吃掉。但是还是有一点舍不得,John打算如果不止一头奶牛最少,当天就大发慈悲,放过所有的牛。由于John的奶牛产奶是周期性的,John在一开始就可以了解所有牛的最终命运,不过他的数学很差,所以请你帮忙,算算最后有多少头奶牛可以幸免于难。每头奶牛的产奶周期T可能不同,但不会超过10种,在每个周期中,奶牛每天的产奶量不超过200.

解决方案

方案一:蛮力法

根据题意,我们需要找出所有奶牛中的最小值,并要计算最小产奶量出现的次数。由于奶牛的产奶周期存在10种情况,所以我们每天都需要重新排序找出最小值和其出现的次数。如果有的牛永远也不会被吃掉,那么我们需要多模拟2520(1、2、3、4、5、6、7、8、9、10的最小公倍数)天的产奶情况才能确定。

方案二:

周期相同的奶牛没有都被吃掉之前,每天的最小产奶量也是相同周期的。因此我们把周期相同的奶牛合并起来,每天就只需比较10类奶牛中每类牛的最小产奶量就可以了。假设周期为6的牛有4头,他们的合并结果如下表所示;

项目

第6n+1天

第6n+2天

第6n+3天

第6n+4天

第6n+5天

第6n+6天

牛1

2

5

3

5

7

4

牛2

3

1

6

7

5

4

牛3

5

3

3

5

3

9

牛4

4

4

3

8

8

2

合并结果

2(牛1)

1(牛2)

3(多牛)

5(多牛)

3(多牛)

2(牛4)

这样一来,在和其他组比较时,如果是第6n+1天,就把牛1拿去比较,因为其他牛都比他大。如果是6n+3天,就把产奶量3拿去比较,如果它是最小的,那么就有多头牛产最少奶,则都不会被吃掉。这样,每次就只需比较10组牛的代表就可以了。

运用的计算思维

从上面的案例中,我们可以发现,如果循着蛮力法的思维解题,可能会耗费大量的时间和精力;而如果在问题上加以处理,转换思路,如上面的案例中就将奶牛进行分组选出代表,将排序比较的过程进行了简化,大大降低了解题的时间,计算思维中的转化思维正是这类问题的一汪清泉。

参考文献

[1] 《算法艺术与信息学竞赛》 清华大学出版社