P8898 [USACO22DEC] Feeding the Cows B 题解.docx
需积分: 0 175 浏览量
2024-02-14
15:55:35
上传
评论
收藏 13KB DOCX 举报
思路
这是一道贪心题。我们先考虑更赛牛。
首先，一个草如果要供最多牛食用，它就要尽可能远离最远的牛，这样才能保证另一端更多
的牛能吃到。这样一格草就能最多满足
2
×
�
+
1
2×k+1 只同一种牛的食用需求。
但是，如果第
�
i 只牛已经靠近另一端，
�
+
�
i+k 已经超出了草地
�
a 的距离，我们就将最后一格草放在草地的最末尾。这样就能放置最少的草地就能满足所有
的更赛牛。
荷斯坦牛的方法显然也类似，要尽可能满足最多的牛，它要尽量放置在
�
+
�
i+k 的位置，这保证和之前不会重复。因为
�
i 位置的牛是唯一的，所以
�
+
�
i+k 位置肯定没有被占用。
我们同时也要考虑荷斯坦牛最后一格草超出边境的问题。因为边界已经被更赛牛占用，我们
就从
�
a 到
1
1 依次遍历找到空的格子放上就行了。一定要遍历到
1
1 或者
�
资源评论
