Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——扫描+优先队列

Posted by fanhqme at 2009-07-17 21:09:56 on Problem 3277 and last updated at 2009-07-17 21:12:09
其实这题可以用线段树

暴力离散化(排序) 或 动态建线段树都可以

不过想用一点不同的方法
从头到尾扫描所有的事件:线段开始与结束
若一个线段的开始小于扫描线,则插入
                ^^^^
若一个线段的结尾小于扫描线,则删除
                ^^^^
然后求H最大值作为当前区间的高度

需要写两个heap,不如线段树来的爽,不过忍了吧

两个“小于”必须想清楚,否则会挂
由于不存在A[i]==B[i],所以插入和删除的顺序是随便的

最后,如果wa掉了,不要忘记看看是否用了long long/int64。这道题真不厚道!又是比赛中欺负C++的好题。

堆+扫描比线段树(不用离散化的那个)的好处是可以对付更大的数据(甚至高精度),而线段树写起来更方便,也不容易错(至少我认为)



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator