CF727F Polycarp’s problems

算法

贪心

思路

考虑特殊情况。当 $m=1$ 时，问题转化为：给定 $a_0$ , 求删除最少元素使得对于任意的 $i$ ，满足 $\Sigma_{j=0}^{i} a_{j} \ge 0$ 。将特殊情况扩展到 $m \le 10^6$ ，即对于每一个给定的 $a_0$ ，求解上述问题。考虑贪心，即对于一个 $i$ ，满足 $\Sigma_{j=0}^{i} a_{j} < 0$ ，则必定删除前面最大的负数，才会使最后的结果最优.于是可以逆向思维，倒序遍历数组 $a$ ，维护一个大根堆(即维护绝对值最小的负数，对于每一个 $a_{i} < 0$ , 将其入队；对于每一个 $a_{i} \ge 0$ ，用 $a_{i}$ 抵消堆顶元素，直到堆为空或 $a_{i} < 0$ 。最后将堆里的元素全部放入一个新数组，即这些负数在 $a_{1} \to a_{n}$ 里都不能被抵消，只能由 $a_{0}$ 抵消，被删除的个数即为剩余负数的个数减去 $a_{0}$ 最多可以抵消的负数，可以二分解决。

代码

1
#include <bits/stdc++.h>
2
#define OnlineJudge
3

4
using namespace std;
5
int main() {
6
  ios::sync_with_stdio(false);
7
  cin.tie(nullptr);
8
  cout.tie(nullptr);
9

10
  int n, m;
11
  cin >> n >> m;
12

13
  vector<long long> a(n), b(m);
14

15
  for (int i = 0; i < n; i++) {
16
    cin >> a[i];
17
  }
18

19
  priority_queue<long long, vector<long long>, less<long long>> q;
20

21
  for (int i = n - 1; i >= 0; i--) {
22
    if (a[i] < 0) {
23
      q.emplace(a[i]);
24
    } else {
25
      while (!q.empty() && a[i] >= 0) {
26
        a[i] += q.top();
27
        q.pop();
28
      }
29

30
      if (a[i] < 0) {
31
        q.emplace(a[i]);
32
      }
33
    }
34
    continue;
35
  }
36

37
  vector<long long> modify;
38

39
  while (!q.empty()) {
40
    modify.emplace_back(-q.top());
41
    q.pop();
42
  }
43

44
  // reverse(modify.begin(), modify.end());
45

46
  for (int i = 1; i < static_cast<int>(modify.size()); i++) {
47
    modify[i] = modify[i] + modify[i - 1];
48
  }
49

50
  #ifndef OnlineJudge
51
  for (auto&& var : modify) {
52
    cout << var << " ";
53
  }
54
  cout << "\n";
55
  #endif
56

57
  for (int i = 0; i < m; i++) {
58
    cin >> b[i];
59

60
    int answer;
61
    if (modify.empty() || modify.back() <= b[i]) {
62
      answer = 0;
63
    } else {
64
      int pos = upper_bound(modify.begin(), modify.end(), b[i]) - modify.begin();
65
      answer = static_cast<int>(modify.size()) - pos;
66
    }
67

68
    cout << answer << '\n';
69
  }
70

71
  return 0;
72
}