夢に僕らで帆を張って
来るべき日のために夜を超え

标签 贪心 下的文章

October 28, 2019

洛谷P1937/USACO10MAR 仓配置Barn Allocation

题意有$n$个点,$m$条线段,每个点最多被覆盖$c_i$次,求最多选择几条线段数据范围:$1 \le n,m,c_i \le 100000$题解先按右端点为第一关键字升序,左端点为第二关键字降序排序随后按顺序选择区间,能选则选正确性证明:在右端点相同时,显然左端点越大区间长度越短,结果越优在右端点不同时,对于先选择的区间$i$与和$i$发生冲突的区间$j$,需要讨论的情况为$$l_i &l...