题解:CF1307E Cow and Treats

· · 题解

首先同一种颜色的牛最多会满足两只。我们可以很简单的求出,一头牛从右边/左边走到达的地方。

这个题要求出一个不算重的方法啊,否则去重太麻烦了。那么我们发现被吃掉的草是一定是先被左边的牛吃,一个分界点后被右边的牛吃。可以枚举这个分界点。然后就不会算重了。

枚举了分界点(第一个左边的牛),首先保证答案最大。发现我们决定了左右以后,我么按照离分界点距离排序了以后一定是可行的,因为有“都不完全相同”这个条件。特别的,不同喜好的牛可以分开考虑。那么,求出左右两边都可以的,只能左边的,只能右边的。计算答案是 trivial 的。

特殊的,有可能一个左边的也没有。