AtCoder Beginner Contest 248 F - Ignore Operations // 贪心 + 大根堆
2022/4/24 6:15:37
本文主要是介绍AtCoder Beginner Contest 248 F - Ignore Operations // 贪心 + 大根堆,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门:F - Keep Connect (atcoder.jp)
题意:
给定长度为N的操作(ti,yi)。
给定初值为0的x,对其进行操作:当t为1时,将x替换为y;当t为2时,将x加上y。
最多可以跳过k步,求最终x的最大值。
思路:
注意到,当t为1时,进行替换操作,那么该位置前面的操作是不会对后面产生任何影响的,也就不会消耗k。
那么我们可以枚举最后一次不跳过的1操作,对于该位置的前面无需考虑,对于该位置的后面:所有的1操作都应跳过(记数量为cnt),且对于2操作选择数值前k - cnt小的跳过。
于是可以从后往前推,同时维护一个大小为k - cnt的大根堆(存跳过的2操作的数值),和一个增加值add(存不跳过的2操作的数值之和),则当每次遇到1操作时,此时的x值为(y + add),动态更新求最大值即可。
代码参考:
#include <bits/stdc++.h> #define LL long long #define PII pair<int,int> #define fi first #define se second using namespace std; const int N = 200010; int n, k; PII a[N]; priority_queue<int> heap; // 维护大根堆 void func(LL& add) { while(heap.size() > k) { add += heap.top(); heap.pop(); } } int main() { cin >> n >> k; for(int i = n; i; i--) cin >> a[i].fi >> a[i].se; LL ans = -1LL << 60, add = 0; for(int i = 1; i <= n; i++) { int t = a[i].fi, y = a[i].se; if(t == 1) { ans = max(ans, y + add); -- k; func(add); } if(t == 2) { if(y >= 0) add += y; else heap.push(y); func(add); } if(k < 0) break; } if(k >= 0) ans = max(ans, add); cout << ans << endl; return 0; }
这篇关于AtCoder Beginner Contest 248 F - Ignore Operations // 贪心 + 大根堆的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升