(2018 CCPC 吉林站 J题)
题意：有n个物品，每个物品可以染成m种颜色之一，而且每个物品染某种颜色的都有不同的权值，用一个矩阵表示。这些物品染色后存在排成环的一种方案，使得同一种颜色在环中不能相邻。问染色方案中权值的极差最小是多少。

又是1000的范围又是染色匹配又是带条件限制很容易让人想歪成二分图或网络流，然而这题跟二分图无关。
首先算极差比较难处理，所以考虑枚举上界和下界。因为枚举上界的过程中下界是单调增加的，所以这部分就是个O(n)的双指针。
然后考虑第二个条件，其实就是说某种颜色的出现次数不能超过n/2。这个条件等价于每个物品有染色方案，而且对于任意一种颜色不能多于n/2个物品必选。之所以等价是因为非必选只要能染色就不会超过n/2。
其实对于不超过n*r (0<=r<=1)这种条件，只要(0.5<=r<=1)都可以用这种方式直接判断。