题目链接

给定一个环，环上有 $n$ 个节点。选出 $m$ 个互不相邻的节点，使得选出节点的权值总和最大。

$n\le 200000$

题目链接

高精度怎能少了Python3题解。。。

贪心策略一楼dalao已经讲得很清楚了，上一发超短代码（学Python就是为了水高精）

题目链接

介绍一种本题的贪心解法。

本题要求读入一些挤牛奶的时间段，求最长至少有一人在挤牛奶的时间段和最长没有人在挤牛奶的时间段。把读入的区间视作线段，则题意转变为求至少有一条线段覆盖的最大区间和没有线段覆盖的区间。

假设读入数据如下：

首先按照4条线段的起点位置排序（具体原因后面解释）。将begin设置为第一条线段的起点，将end设置为第一条线段的终点。

然后从第二条线段开始判断。如果该线段的起点小于end，则说明这两条线段有重合部分，将end更新为max{end,该线段的终点位置}。如果该线段的起点大于end，则说明该线段及以后的线段再也不会与前面的线段产生任何重合部分（这也就是排序的作用），那么可以更新ans1和ans2的值：ans1更新为max{ans1,end-begin},ans2更新为max{ans2,该线段的起点位置-end}。具体参见图中第4条线段，ans1被更新为1200-0，ans2被更新为1400-1200。

程序已经基本成型，但要注意在输出答案前更新一遍ans1的值，这是为了避免所有线段均有重合部分而无法判断的情况。另外，ans1和ans2要初始化为0。

程序如下：