与前缀和有关的问题

（不懂算不算前缀和）

模型：n 个数围成一圈，要求从一个数出发，顺时针走一圈并不断加上经过的数，使得到的和总是非负。

要求O(n)判断是否有解，并找到出发点。

题例：LuoguP7590，HDU 6205

首先很明显的一点是，如果 n 个数的总和是负数，那肯定无解。

如果总和非负，是否一定有解？是的，接下来证明：

设 n 个数的总和为 sum，

我们从任意一个数出发，按照要求顺时针走，并不断加上沿途的数

• 如果一直走完了都是非负数，那就找到解了咯
• 如果走到一个地方变成负数了，把这个地方记下来，并从下一个数重新出发

（如下图，从s1出发，走到s2前一个数时得到了-x1，于是从s2重新出发）

我们按照这个规则一直走，直到到达s1为止，看看会发生什么

直到走到sk，我们一共负了很多很多的xi，而又有所有这些负数加起来再加xk等于sum

所以如果sum>=0，那么xk就足以将所有这些负数填满，所以最后一定能找到这样一个sk，走一圈经过的和总非负

然后起点的找法也知道了，就从1开始找就行了。