先考虑无解的情况，来看样例三，很容易发现是因为\(k\)太大了，所以每次都会修改之前已经改好的。于是我们猜想，如果任意一段连续的数的长度都小于\(k\)，那么就无解，证明比较容易，反证就好了，如果存在一个解，那么这个解的最后一步操作，一定是连续的\(k\)个格子，而且这\(k\)个格子的颜色一定要一样，与我们前面的条件矛盾，所以无解；于是我们猜想如果存在一个连续段长度大于等于\(k\)，那么一定有解，我们假设只有一个连续段，然后考虑从这个连续段入手，除了这个连续段，剩下的连续段的长度都小于\(k\)，我们依次涂每个连续段，最后再涂这个最长的连续段，显然是一个解；拓展到多个连续段的情况，对于两个长度大于等于\(k\)的连续段之间的连续段（长度都小于\(k\)），我们按照上面的方法涂，然后最后涂大的连续段，就是一个解，而且可以发现这个解是最优解，来证明一下
对一个长度为\(len\)的连续段，将其覆盖最少需要\(\lceil \frac{len}{k}\rceil\)次，那么下界就是所有这种连续段的和，显然我们上面的方法可以达到这个下界
代码可以看看，为了避免麻烦，我们断环成链的时候选取两个相邻且不同的数之间断开就好了
标签：Heirloom,len,连续,长度,Painting,我们 From： https://www.cnblogs.com/dingxingdi/p/18133759