Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
雁过留声——扫描+优先队列其实这题可以用线段树 暴力离散化(排序) 或 动态建线段树都可以 不过想用一点不同的方法 从头到尾扫描所有的事件:线段开始与结束 若一个线段的开始小于扫描线,则插入 ^^^^ 若一个线段的结尾小于扫描线,则删除 ^^^^ 然后求H最大值作为当前区间的高度 需要写两个heap,不如线段树来的爽,不过忍了吧 两个“小于”必须想清楚,否则会挂 由于不存在A[i]==B[i],所以插入和删除的顺序是随便的 最后,如果wa掉了,不要忘记看看是否用了long long/int64。这道题真不厚道!又是比赛中欺负C++的好题。 堆+扫描比线段树(不用离散化的那个)的好处是可以对付更大的数据(甚至高精度),而线段树写起来更方便,也不容易错(至少我认为) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator