• <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,很多同學(xué)對(duì)題意理解有誤(剛開始我也理解錯(cuò)了)
            主要是這句: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

            成為猴王的條件是,沒(méi)有任何的一個(gè)猴子的x坐標(biāo)和y坐標(biāo)都大于它,而不是說(shuō)猴王的x和y都要最大.
            ok,算法也出來(lái)了,簡(jiǎn)單地說(shuō): 先對(duì)x快速排序,然后統(tǒng)計(jì)y  , 時(shí)間效率是O(n^lgn)
            具體細(xì)節(jié)要自己體會(huì),這題挺經(jīng)典的.另外快速排序的方法,雖然我也不是第一次用到了,但是仍然不熟練,到網(wǎng)上查了語(yǔ)法再做的.
            #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;           //最后一個(gè)猴子的x最大,所以至少有一個(gè)猴王. 往前掃描,如果出現(xiàn)某個(gè)猴子的y大于當(dāng)前最大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上編譯器效率的問(wèn)題:

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

            也就是說(shuō),同樣的測(cè)試數(shù)據(jù),要達(dá)到最好的效率,應(yīng)該用純C的方式寫程序,并選擇C++編譯器judge程序.

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

            評(píng)論

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

            這題題目改了吧。。。你這代碼過(guò)不了。  回復(fù)  更多評(píng)論   

            # re: ACM PKU 1828 Monkeys' Pride 2009-08-01 09:33 幻風(fēng)

            明顯過(guò)不了吧?
            4
            3 1
            3 2
            3 0
            2 2
              回復(fù)  更多評(píng)論   

            # 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>.  回復(fù)  更多評(píng)論   

            # 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.   回復(fù)  更多評(píng)論   

            # 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.   回復(fù)  更多評(píng)論   

            # 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.  回復(fù)  更多評(píng)論   

            # 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.   回復(fù)  更多評(píng)論   

            # 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.   回復(fù)  更多評(píng)論   

            # 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+.   回復(fù)  更多評(píng)論   


            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            <2012年4月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導(dǎo)航

            統(tǒng)計(jì)

            公告

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

            常用鏈接

            留言簿(6)

            隨筆檔案

            相冊(cè)

            搜索

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            一本色道久久99一综合| 伊人丁香狠狠色综合久久| 久久99精品久久久久久不卡| 93精91精品国产综合久久香蕉 | 97久久国产亚洲精品超碰热| 欧美久久精品一级c片片| 亚洲国产视频久久| 91精品国产91久久久久久青草| 亚洲国产成人久久综合一| 久久久久久国产精品美女| 精品免费久久久久国产一区| 亚洲中文字幕无码久久精品1| 人人狠狠综合久久亚洲88| 97精品依人久久久大香线蕉97| 国产精品狼人久久久久影院| 久久99精品久久久久久久不卡| 久久久久久免费视频| 久久香蕉一级毛片| 蜜臀久久99精品久久久久久小说 | 久久亚洲欧美国产精品 | 久久99精品国产自在现线小黄鸭 | 国内精品久久人妻互换| 性做久久久久久免费观看| 久久精品成人国产午夜| 99久久国语露脸精品国产| 国产欧美久久久精品影院| 人妻无码久久精品| 色综合合久久天天综合绕视看| 色88久久久久高潮综合影院| 综合久久久久久中文字幕亚洲国产国产综合一区首 | 久久www免费人成看国产片| av无码久久久久久不卡网站| 亚洲中文字幕无码一久久区 | 大伊人青草狠狠久久| 久久中文骚妇内射| 婷婷久久久亚洲欧洲日产国码AV| 日本五月天婷久久网站| 中文成人久久久久影院免费观看 | 亚洲精品视频久久久| 久久久久婷婷| 久久夜色精品国产亚洲|