Hello 2023
C. Least Prefix Sum
思路：
仔细看式子，发现可以对它进行推理（ m m m 是定值， 1 ≤ k ≤ n 1\le k\le n 1≤k≤n ）：
- 当 k ≤ m k\le m k≤m 时，有 a 1 + a 2 + ⋯ + a k ≥ a 1 + a 2 + ⋯ + a m a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m a1+a2+⋯+ak≥a1+a2+⋯+am 0 ≥ a k + 1 + a k + 2 + ⋯ + a m 0 \ge a_{k+1} + a_{k+2} + \cdots + a_m 0≥ak+1+ak+2+⋯+am所以我们需要每个 [ k + 1 , m ] [k+1,m] [k+1,m] 区间的和都 ≤ 0 \le 0 ≤0， ( 1 ≤ k ≤ m ) (1\le k\le m) (1≤k≤m)。
- 当 k > m k\gt m k>m 时，有 a 1 + a 2 + ⋯ + a k ≥ a 1 + a 2 + ⋯ + a m a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m a1+a2+⋯+ak≥a1+a2+⋯+am a m + 1 + a m + 2 + ⋯ + a n ≥ 0 a_{m+1} + a_{m+2} + \cdots + a_n \ge 0 am+1+am+2+⋯+an≥0所以我们需要每个 [ m + 1 , n ] [m+1,n] [m+1,n] 区间的和都 ≥ 0 \ge 0 ≥0， ( 1 ≤ k ≤ m ) (1\le k\le m) (1≤k≤m)。
先看第一种情况，怎么用最小的操作次数维护这个性质呢？一种贪心的想法是从 m m m 向 2 2 2 看，如果满足条件就不动，如果不满足条件就选一个最大的数把它变成负的即可。这样跑一遍，操作的次数就是最少的。
怎么保证最大的数一定是正数，从而变负数呢？而且只操作一次即可呢？因为前面都满足条件，区间和为负数，到这个数就不满足条件了，所以这个数一定是正数，把它变负一定整个区间和都变成负数，我们去找更大的数变负，显然更满足条件。
第二种情况同理。这两种情况互不影响，所以贪心策略是正确的。维护最大值和最小值可以用优先队列或者 m u l t i s e t multiset multiset，不过 m u l t i s e t multiset multiset 使用 e r a s e erase erase 成员函数进行值的删除的时候，会把所有相同的值同时删除，所以要用 S . e r a s e ( S . f i n d ( x ) ) S.erase(S.find(x)) S.erase(S.find(x)) 的写法（迭代器删除）。
code：
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
int T,n,m,a[maxn];
int main(){
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
multiset<int> S;
int cnt=0;
ll tot=0;
for(int i=m;i>=2;i--){
S.insert(a[i]);
tot+=a[i];
if(tot>0){
ll t=*S.rbegin();
S.erase(S.find(t));
tot-=t;
t=-t;
tot+=t;
S.insert(t);
cnt++;
}
}
S.clear();
tot=0;
for(int i=m+1;i<=n;i++){
S.insert(a[i]);
tot+=a[i];
if(tot<0){
ll t=*S.begin();
S.erase(S.begin());
tot-=t;
t=-t;
tot+=t;
S.insert(t);
cnt++;
}
}
cout<<cnt<<endl;
}
return 0;
}