`
huobengluantiao8
  • 浏览: 1022087 次
文章分类
社区版块
存档分类
最新评论

线段树_POJ2528_解题报告

 
阅读更多

题意:给定一些海报,可能互相重叠,告诉你每个海报宽度(高度都一样)和先后叠放次序,问没有被完全盖住的海报有多少张。海报最多10,000张,但是墙有10,000,000块瓷砖长。海报端点不会落在瓷砖中间。

题解:这是一个区间覆盖的问题,由于海报的数量最大有10,000张,O(n^2)的暴力算法是达不到时限要求的,用O(nlgn)的线段树来做应该时间上不会有问题了,但是

直接做线段树会超内存,所以先要离散化一下。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics