题解 | 显生之宙

方法一：模拟、贪心、差分

先考虑暴力，由于有区间修改，想到使用差分进行模拟。模拟的时候可以贪心地想到：

若当前的最小值是负数，为了最小化最后的结果，就将后续的所有数全都加上这个负数；若当前的最小值不是负数，那么只找一个数加上，为了方便，就找第一个大于等于它的数即可。

因此需要先对数组a排序，且中间加的过程应该使用差分，边修改边计算，最后遍历到的数a[i]就是答案。

总时间复杂度为O(n * logn)，瓶颈主要在排序上，遍历加差分的时间复杂度仅为O(n)。

#include <iostream>
#include <vector>
#include <algorithm>

using i64 = long long;

void solve(){
  int n;
  std::cin >> n;

  std::vector<i64> a(n + 1), diff(n + 3);
  for(int i = 1; i <= n; i++){
    std::cin >> a[i];
  }

  std::sort(a.begin() + 1, a.end());

  auto update = [&](int l, int r, i64 x){
    diff[l] += x;
    diff[r + 1] -= x;
  };

  for(int i = 1; i <= n; i++){
    diff[i] += diff[i - 1];
    a[i] += diff[i];
    if(a[i] < 0){
      update(i + 1, n, a[i]);
    }else{
      update(i + 1, i + 1, a[i]);
    }
  }

  std::cout << a.back() << "\n";
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int T = 1;
  std::cin >> T;

  for(int Ti = 0; Ti < T; Ti++){
    solve();
  }

  return 0;
}

方法二：方法一的优化，将差分数组优化成两个变量

cur记录前缀负数的贡献，next记录上一个正数的贡献。

#include <iostream>
#include <vector>
#include <algorithm>

using i64 = long long;

void solve(){
  int n;
  std::cin >> n;

  std::vector<i64> a(n + 1);
  for(int i = 1; i <= n; i++){
    std::cin >> a[i];
  }

  std::sort(a.begin() + 1, a.end());

  i64 cur = 0, next = 0;

  for(int i = 1; i <= n - 1; i++){
    i64 val = a[i] + cur + next;
    if(val < 0){
      cur += val;
      next = 0;
    }else{
      next = val;
    }
  }

  std::cout << a.back() + cur + next << "\n";
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int T = 1;
  std::cin >> T;

  for(int Ti = 0; Ti < T; Ti++){
    solve();
  }

  return 0;
}