网站首页
编程语言
数据库
系统相关
其他分享
编程问答
Haybales
2024-11-14
P8099 [USACO22JAN] Minimizing Haybales P 题解
好题图论的难点在于建图~首先我们关注到如果两个草堆之间的差大于K,那么他们的位置就是固定的,就相当于给了一些限制,这就是很经典的连边然后拓扑排序。其实你是不是可以直接从小的向大的连边(我没试)然后再做排序。这一部分代码(粗略验证正确性,赶着写的,可能比较一言难尽)#include<bi
2024-11-06
[USACO22JAN] Minimizing Haybales P 题解
[USACO22JAN]MinimizingHaybalesP随机化?五分。显然对于任意\(a_i,a_j\),若\(|a_i-a_j|>K\),则这两堆草的先后顺序永远不会改变。所以易得暴力:对于所有这样的\(i,j\),不妨设\(i<j\),则连一条\(i\toj\)的边,答案就是这个图字典序最小的拓扑排序,优先队列即可。voidtoposort(