考虑枚举线段的中点，计算它对答案的贡献。时间复杂度 \(O(nm)\)。
首先可以计算出最大流量 \(maxf=\dfrac{sum}{len}\)。
那么就可以将 \(k\) 条路径当成一条来看。把每条路径的容量，从小到大排序，然后把 \(k\) 条路径合在一起。此时，平均流量和总容量的差值，就是需要操作的次数。
这里我们无需关心，这个操作是怎么实现的，只需要关注当前状态和最终状态之间的差值即可。
考虑如果存在答案，一定有两个元素在 \(a\) 中位置的差值不超过 \(2\)。因此可以随机找这个位置，\(O(n)\) 来 check，多做几次能够大概率正确。
对于数 \(x\)，令 \(k\) 为最大的满足存在整数 \(y\) 使得 \(y^k=x\) 的数，把 \(x\) 放进第 \(k\) 组。容易发现只有组内的数才会互相影响，所以对于每个组都暴力枚举每个数选或不选，把每个组的答案相加即可。
时间复杂度不大于 \(O(n\sqrt n)\)，但具体的复杂度我不会证。
标签：1.14,题解,复杂度,路径,枚举,差值,模拟 From： https://www.cnblogs.com/Tarantula/p/1-14-p.html