题解 P8099 [USACO22JAN] Minimizing Haybales P
2022/2/5 6:15:16
本文主要是介绍题解 P8099 [USACO22JAN] Minimizing Haybales P,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
提供一个无脑做法。是目前最劣解……
考虑两个草堆 \(x,y\) 若满足 \(x<y\) 且 \(|h_x-h_y|>K\),那么显然无论怎么交换 \(x\) 永远在 \(y\) 前面。因此我们对于每一个这样的 \(x,y\),从 \(x\) 向 \(y\) 连边。
答案应该是建出的图的最小字典序(权值是 \(h\))的拓扑序。这样很明显是 \(n^2\) 的算法,我们考虑优化建图。
考虑绝对值拆开。考虑按照 \(h\) 的大小依次把每个点加入线段树,于是对于 \(y\) 这个点加边的时候,只要考虑前面某棵线段树(满足所有 \(h_i<h_y-K\))的区间 \([1,y]\) 加边就行了。可以用 lower_bound 找到这棵线段树。
这里我就写了主席树。当然由于绝对值,反过来也要跑一遍。于是建完图跑一下拓扑序就行了。
时间复杂度应当是 \(O(n\log n)\) 的,但是常数似乎巨大。
这篇关于题解 P8099 [USACO22JAN] Minimizing Haybales P的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!