前言
很好玩的贪心。
思路
如果第 \(i\) 次操作为覆盖操作，那么 \(1 \sim i-1\) 次操作都是无效的，原因显然。
这启示我们从后往前扫（前面的会被忽略，后面的不会啊！）。
在此基础上，就是分类讨论一下（假设当前的最大答案为 \(sum\)）：
- 当前操作是覆盖操作：
- 如果不删 \(a_i\)，那么 \((sum + a_i)\) 就是最终答案，因为更前面的操作会被省略。
- 如果删 \(a_i\)，那么这次操作无效，但是能操作的次数少了。所以 \(k \gets k-1\)，继续。
- 当前操作时增加操作：
- 如果 \(a_i \ge 0\)，加了肯定时好的，所以直接 \(sum \gets sum + a_i\)。
- 如果 \(a_i < 0\)，加了肯定变差，所以我们试图不加它。但是当不加的数量超过 \(k\) 时，不得不把某些操作重新加上。
对于最后一项，我们可以把 \(sum\) 重新加上当前最大的元素。所以只需要一个优先队列，当 \(\text{size} > k\) 时就扔掉 \(\max\limits_{x \in \text{queue}} x\)。
当 \(k < 0\) 的时候就不能操作了，请直接退出程序。另外操作完全部后，\(sum\) 也是可以作为答案的，记得更新一下。
代码
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 2e5 + 5;
int op[N], a[N];
int main()
{
priority_queue <int> q;
int n, k;
long long ans = -9e18, sum = 0;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d%d", &op[i], &a[i]);
for (int i = n; i && ~k; i--)
{
if (op[i] == 1) ans = max(ans, a[i] + sum), k--;
else if (op[i] == 2)
{
if (a[i] >= 0) sum += a[i];
else q.push(a[i]);
}
while ((int)q.size() > k) sum += q.top(), q.pop(); //把比较大的元素扔掉
}
cout << max(ans, sum);
return 0;
}
希望能帮助到大家！