链接
https://codeforces.com/problemset/problem/1779/C
题目
思路
1-m的前缀和最小。那么显然知道[1,m-1]的前缀和更大，所以a[m]<0,同理a[m-1]+a[m]<0，...，a[2]+...+a[m]<0。采用大根堆优先队列管理其中的值，如果上面的任何一个大于零，弹出优先队列的top，减掉两倍的top，让他重新变成负数即可，然后计数器ans++。对m后半段的序列同理操作代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#define IOS ios::sync_with_stdio(false), cin.tie(0) ,cout.tie(0)
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N];
signed main()
{
IOS;
int t; cin >> t;
while (t--)
{
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
priority_queue<int>pq;
int sum1 = 0;
int ans = 0;
for (int i = m; i > 1; i--)
{
pq.push(a[i]);
sum1 += a[i];
if (sum1 > 0)
{
ans++;
int top = pq.top();
pq.pop();
sum1 -= 2 * top;
pq.push(-top);
}
}
priority_queue<int, vector<int>, greater<int>>pq2;
sum1 = 0;
for (int i = m + 1; i <= n; i++)
{
pq2.push(a[i]);
sum1 += a[i];
if (sum1 < 0)
{
ans++;
int top = pq2.top();
pq2.pop();
sum1 -= 2 * top;
pq.push(-top);
}
}
cout << ans << '\n';
}
return 0;
}