Detail of message

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

难道这题有比nlogn更快的算法？同样是nlogn，不会我的TLE，几十ms吧。。。

Posted by js05 at 2005-05-13 14:13:17 on Problem 2352

Followed by:

显然每个点做一次，就O(n)了，难道可以O(1)时间维护？ (0) js05 2005-05-13 14:14:14
- nlogn，用线段树做 (0) frkstyc 2005-05-13 14:17:10
  - 只能用线段树？我的方法效率也不是很低啊。。。 (0) js05 2005-05-13 14:47:37
    - 也许我还没搞懂线段树。。。 (0) js05 2005-05-13 14:51:01
    - 你怎么做的？ (0) frkstyc 2005-05-13 14:53:51
      - 见内。。。 (64) js05 2005-05-13 15:08:07
        具体是怎么样？ (70) frkstyc 2005-05-13 15:10:52
        我不太说得清楚，您一看代码就明白了。。。 (1849) js05 2005-05-13 15:11:07
        TLE是事实，但我想搞清楚，为什么会这么慢。。。 (2081) js05 2005-05-13 15:12:40
        我还是换线段树吧，请各位赐教为什么这方法这么慢。。。 (0) js05 2005-05-13 15:19:50
        怎么要排序？用不着吧？连纵坐标都可以不用的，只要一个x就够了 (0) frkstyc 2005-05-13 15:23:52
        怎么搞，我不明白。。。 (0) js05 2005-05-13 15:25:26
        p1<p2，不是要p1.x<=p2.x and p1.y<=p2.y 吗？ (0) js05 2005-05-13 15:26:25
        数据保证先对y有序然后对x有序 (0) frkstyc 2005-05-13 15:27:46
        原来是这样。。。没好好读题，傻了。。。 (0) js05 2005-05-13 15:29:06
        拿qsort去排顺序的数据肯定超时了 (0) frkstyc 2005-05-13 15:29:45
        不过我qsort的时候随机了呀，效率也不应该差这么多。。。 (0) js05 2005-05-13 15:40:04
        那你不如用冒泡去排，跑一趟就可以停下来了 (0) frkstyc 2005-05-13 15:44:45
        哈哈，确实！总之，我干了一件SB的事情。。。 (0) js05 2005-05-13 15:51:34
        把排序整段拿掉就基本上可以了，可能在边界处要调整一下 (0) frkstyc 2005-05-13 15:27:07
        我也是这样做的，C写的105ms，汇编好像也好不了多少，90ms (2081) frkstyc 2005-05-13 15:22:35
        PASCAL和C的效率差这么多？ (0) js05 2005-05-13 15:24:06
        Re:见内。。。 (70) scu05p27 2006-03-08 11:18:29
        Re:见内。。。 (101) scu05p27 2006-03-08 11:20:21

Post your reply here:

Home Page Go Back To top