前言
很好玩的贪心。
思路
如果第 \(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;
}
希望能帮助到大家!
标签:int,题解,sum,text,操作,include,ABC249F From: https://www.cnblogs.com/liangbowen/p/17320550.html