• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ACM PKU 1828 Monkeys' Pride

            http://acm.pku.edu.cn/JudgeOnline/problem?id=1828
            看了discuss,很多同學對題意理解有誤(剛開始我也理解錯了)
            主要是這句:If a monkey lives at the point (x0, y0), he can be the king only if there is no monkey living at such point (x, y) that x>=x0 and y>=y0

            成為猴王的條件是,沒有任何的一個猴子的x坐標和y坐標都大于它,而不是說猴王的x和y都要最大.
            ok,算法也出來了,簡單地說: 先對x快速排序,然后統計y  , 時間效率是O(n^lgn)
            具體細節要自己體會,這題挺經典的.另外快速排序的方法,雖然我也不是第一次用到了,但是仍然不熟練,到網上查了語法再做的.
            #include"stdio.h"
            #include
            "stdlib.h"

             
             typedef 
            struct{
                
            int x;
                 
            int y;
             }
            node[50001];
             


             
            int cmp(const void *pl, const void *pr){   ///按照x從小到大排序
                node *p1 = (node*)pl; 
                 node 
            *p2 = (node*)pr;
                 
            if(p1->== p2->x)           
                     
            return p1->- p2->y;
                
            return p1->- p2->x;
             }

             

            void main(){
                 
            int num,i,total,maxy;
                 
            while(scanf("%d",&num) && num){
                     
            for(i=0;i<num;i++)
                         scanf(
            "%d%d",&nodes[i].x,&nodes[i].y);
                     qsort(nodes, num, 
            sizeof(node), &cmp); //按照x從小到大排序
                   total=1;           //最后一個猴子的x最大,所以至少有一個猴王. 往前掃描,如果出現某個猴子的y大于當前最大y,total+1
                     maxy=nodes[num-1].y;
                    
            for(i=num-2;i>=0;i--){
                         
            if(maxy<nodes[i].y){
                            maxy
            =nodes[i].y;
                             total
            ++;
                         }

                     }

                     printf(
            "%d\n",total);
                 }

                 
            return;
             }



            另外,在PKU上編譯器效率的問題:

            同樣的程序,我測試了3次.
            include的時候,如果用iostream,在  C++編譯器下測試,Memory是476K ,時間280MS
            換成 stdio.h + stdlib.h ,在C編譯器下Memory是464K ,時間171MS
            如果是stdio.h + stdlib.h在C++的編譯器下測試呢?Memory是464K ,時間155MS

            也就是說,同樣的測試數據,要達到最好的效率,應該用純C的方式寫程序,并選擇C++編譯器judge程序.

            posted on 2007-09-21 01:14 流牛ζ木馬 閱讀(1794) 評論(8)  編輯 收藏 引用

            評論

            # re: ACM PKU 1828 Monkeys' Pride 2008-12-02 18:12 aa

            這題題目改了吧。。。你這代碼過不了。  回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2009-08-01 09:33 幻風

            明顯過不了吧?
            4
            3 1
            3 2
            3 0
            2 2
              回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2010-07-09 00:15 WallacePatti29

            This is what I was exploring for a while! Thank you for this topic around college! Once someone state that In union there is might. Our high qualified team can help you in writing <a href="http://essaysexperts.com/">term paper</a>.  回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2010-07-09 16:43 dissertation writing service

            Your well done article about this post comes side by side with the student dissertation. Hence, you must perform for dissertation service.   回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2010-07-09 17:29 thesis

            Eventually, We have found best article just about this good post? We suggest to search the buy thesis or purchase french dissertation, just because this helps in getting the best grade if you have buy dissertation.   回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2010-09-06 14:54 resume writing service

            The clients rely on our
            resume service cause they are very responsible! This corporation performs resume writing to fit the precise field of science you wish.  回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2010-10-07 14:55 buying essays

            To have good grades, some students have to decide if they are willing to accomplish the custom essay paper online or buy an essay paper of the best upper-class.   回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2012-01-13 07:40 book reports

            University students would not have complications with their wars essays creating, because the papers writing corporations are able to sell essay of high quality.   回復  更多評論   

            # re: ACM PKU 1828 Monkeys' Pride 2012-04-17 19:04 buy essay

            Some time before I faced a lot of complications with essays writing. Nevertheles, my friend suggested to buy essays online. Thus, at this moment I have my A+.   回復  更多評論   

            <2008年12月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            導航

            統計

            公告

            MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木馬

            常用鏈接

            留言簿(6)

            隨筆檔案

            相冊

            搜索

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            伊人久久亚洲综合影院| 国内精品久久人妻互换| 久久久久久国产a免费观看不卡| 亚洲欧美精品一区久久中文字幕| 久久久久人妻一区精品色| 婷婷久久五月天| 精品久久久久久| 色综合久久88色综合天天 | 99久久er这里只有精品18| 久久午夜福利电影| 欧美精品丝袜久久久中文字幕| 中文字幕日本人妻久久久免费 | 亚洲国产成人久久综合野外| 免费国产99久久久香蕉| 香蕉久久夜色精品国产尤物| 久久久久久精品免费看SSS| 久久久久亚洲精品天堂| 狠狠色婷婷久久一区二区三区| 精品999久久久久久中文字幕| 久久综合国产乱子伦精品免费| 色诱久久av| 9191精品国产免费久久| 久久精品国产亚洲7777| 伊人久久综合精品无码AV专区| 亚洲va久久久噜噜噜久久| 久久亚洲春色中文字幕久久久| 偷偷做久久久久网站| 精品国产乱码久久久久久1区2区| 亚洲国产精品狼友中文久久久 | 99蜜桃臀久久久欧美精品网站 | 99久久99久久精品免费看蜜桃| 亚洲伊人久久综合影院| 国产精品免费久久久久影院 | 久久丫精品国产亚洲av不卡| 久久强奷乱码老熟女网站| 久久久久久亚洲精品无码| 99久久精品免费看国产一区二区三区| 久久水蜜桃亚洲av无码精品麻豆 | 亚洲天堂久久久| 亚洲精品综合久久| 久久无码高潮喷水|