题目链接: https://vjudge.net/contest/540876#problem/D

题意

给一个长度为 n 的数组 {ai}。现在要令数组中的第 f 个前缀和成为最小的前缀和。可以将数组中的某个元素 ai 变成它的相反数，求最小的操作次数。

思路

考虑一个数组 [a1, a2, a3, {af}, a5, ... , an]，其前缀和数组 [s1, s2, s3, {sf}, s5, ... , sn]。要让 sf 成为所有 si 中最小的元素。

根据这个条件，有

• (af <= 0) sf = s3+af <= s3
• (a3+af <= 0) sf = s2+a3+af <= s2
• (a2+a3+af <= 0) sf = s1+a2+a3+af <= s2
• (a2+a3+af <= 0) sf = a1+a2+a3+af <= s1

所以从 af 向前到 a2 的每一个前缀和都需要小于 0。

同理有

• (a5 >= 0) s5 = sf+a5 >= sf
• (a5+a6 >= 0) s6 = sf+a5+a6 >= sf
• (a5+a6+a7 >= 0) s7 = sf+a5+a6+a7 >= sf
• ...
• (a5+..+an >= 0) sn = sf+a5+..+an >= sf

所以从 a(f+1) 向后的每一个前缀和都要大于 0。

具体代码就是维护一个优先队列，把对一个操作数置反的收益放入队列。每次前缀和不满足条件的时候把队列顶部的元素拿出来加到前缀和里面。

时间复杂度为 O(n·logn)。

代码

#include <iostream>
#include <queue>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          std::cout << '\n';

const int maxN = 2e5+5;
int arr[maxN];

int main() {
  std::ios::sync_with_stdio(0); std::cin.tie(0);
  int t; std::cin >> t;
  while(t--) {
    int n, f; std::cin >> n >> f;
    orep(i, 1, n+1) { std::cin >> arr[i]; }

    int ret = 0;

     {
      long long sum = 0;
      std::priority_queue<long long> q;
      for(int i = f; i > 1; --i) {
        sum += arr[i];
        q.push(2*arr[i]);
        while (sum > 0) {
          sum -= q.top(); q.pop();
          ret++;
        }
      }
    }

    {
      long long sum = 0;
      std::priority_queue<long long> q;
      for(int i = f+1; i <= n; ++i) {
        sum += arr[i];
        q.push(-2*arr[i]);
        while (sum < 0) { 
          sum += q.top(); q.pop();
          ret++;
        }
      }
    }
    std::cout << ret; NL;
  }

  return 0;
}