CF链接：Least Prefix Sum

Luogu链接：Least Prefix Sum

$ {scr color {CornflowerBlue}{ ext{Solution}}} $

先来解释一下题意：

给定一个数组，问最少把多少个数变成相反数，使得$ forall cal{i}$,$ sum_{k=1}^i a_k$ $ le$ $ sum_{k=1}^m a_k$

发现对于所有数据点，$ cal{n} le 2 imes 10^5$，说明需要 $ Ο(cal{n log n}) $ 或者 $ O(cal{n}) $的算法。

分析一下题目，发现要分成$ cal{i} > cal{m}$ 与$ cal{i} < cal{m}$两种情况分类讨论

• 当 $cal{i}$ $ > cal{m}$时：

什么时候才能使$ sum_{k=1}^i a_k$ $ le$ $ sum_{k=1}^m a_k$ 成立呢？

是不是只要使新加的每一段都小于等于0就行了？（$ sum_{k=m}^i a_k$ $ le$ $ 0$）

也很好证明：一个数（$ sum_{k=1}^m a_k$）加上一个小于等于0的数（$ sum_{k={m+1}}^i a_k$），一定不大于原数。

• 当 $cal{i}$ $ < cal{m}$时：

同理，只要使后加的每一段都小于等于0就行了（$ sum_{k=i}^i a_k$ $ ge$ $ 0$）

也很好证明：一个数（$ sum_{k=1}^i a_k$）加上一个大于等于0的数（$ sum_{k=i}^m a_k$），一定不小于原数。

而且，由于这两种情况类似（博主太懒），那就只考虑当 $cal{i}$ $ > cal{m}$的情况吧。

问题已经转化完了，接下来怎么办？

第一眼想到的是贪心。

设当前要取第$cal{i}$个。

有一个不成熟的贪心：如果目前累加和加上$a_i$还是小于等于$0$的，就加上$a_i$，如果大于$0$了，就把$a_i$取反，$ ans+1$。

Hack数据

5 1
1 -1000 999 2 3