• <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>
            posts - 74,  comments - 33,  trackbacks - 0

            Beautiful People
            The most prestigious sports club in one city has exactly N members. Each of its members is strong and beautiful. More precisely, i-th member of this club (members being numbered by the time they entered the club) has strength Si and beauty Bi. Since this is a very prestigious club, its members are very rich and therefore extraordinary people, so they often extremely hate each other. Strictly speaking, i-th member of the club Mr X hates j-th member of the club Mr Y if Si <= Sj and Bi >= Bj or if Si >= Sj and Bi <= Bj (if both properties of Mr X are greater then corresponding properties of Mr Y, he doesn??t even notice him, on the other hand, if both of his properties are less, he respects Mr Y very much).

            To celebrate a new 2005 year, the administration of the club is planning to organize a party. However they are afraid that if two people who hate each other would simultaneouly attend the party, after a drink or two they would start a fight. So no two people who hate each other should be invited. On the other hand, to keep the club prestige at the apropriate level, administration wants to invite as many people as possible.

            Being the only one among administration who is not afraid of touching a computer, you are to write a program which would find out whom to invite to the party.


            This problem contains multiple test cases!

            The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

            The output format consists of N output blocks. There is a blank line between output blocks.


            Input

            The first line of the input file contains integer N - the number of members of the club. (2 <= N <= 100 000). Next N lines contain two numbers each - Si and Bi respectively (1 <= Si, Bi <= 109).


            Output

            On the first line of the output file print the maximum number of the people that can be invited to the party. On the second line output N integers - numbers of members to be invited in arbitrary order. If several solutions exist, output any one.


            Sample Input

            1

            4
            1 1
            1 2
            2 1
            2 2


            Sample Output

            2
            1 4


            Author: Andrew Stankevich
            很猥瑣的最長上升子序列,寫的很猥瑣 ,輸出為給出序列的序號,因為這個錯了幾次 開始的時候二分寫錯一直TLE
            部分代碼如下

            ?

            #include < cstdio >
            #include
            < cstring >
            #include
            < algorithm >
            #define ?MAXN?120000
            using ? namespace ?std;
            struct ?NODE {
            ????
            int ?x,y,mark;
            }
            arr[MAXN],num[MAXN];
            bool ?OK;
            int ?pre[MAXN],root[MAXN];
            int ?n,top,max_sum,best_road;
            int ?Search( int ?now) {
            ????
            int ?left = 0 ,right = top,mid;
            ????
            while (left < right) {
            ????????mid
            = (right + left) >> 1 ;
            ????????
            if (num[mid].y >= now)right = mid;
            ????????
            else ?left = mid + 1 ;
            ????}

            ????mid
            = (left + right) >> 1 ;
            ????
            return ?mid;????
            }

            bool ?cmp(NODE?a,NODE?b) {
            ????
            if (a.x != b.x) return ?a.x < b.x;
            ????
            return ?a.y < b.y;????
            }

            void ?PRINT( int ?x) {
            ????
            if (pre[x])PRINT(pre[x]);
            ????
            if (OK)printf( " ? " );
            ????
            else ?OK = true ;
            ????printf(
            " %d " ,arr[x - 1 ].mark);
            }

            int ?main() {
            ????
            int ?cases,i,j,now;
            ????scanf(
            " %d " , & cases);
            ????num[
            0 ].x = num[ 0 ].y = 0 ;
            ????
            while (cases -- ) {
            ????????max_sum
            = 0 ,top = 1 ;
            ????????scanf(
            " %d " , & n);
            ????????
            for (i = 0 ;i < n;i ++ ) {
            ????????????arr[i].mark
            = i + 1 ;
            ????????????scanf(
            " %d?%d " , & arr[i].x, & arr[i].y);????
            ????????}

            ????????sort(arr,arr
            + n,cmp);
            ????????memset(pre,
            0 , sizeof (pre));
            ????????memset(num,
            0 , sizeof (num));
            ????????
            for (i = 0 ;i < n;i ++ ) {????
            ????????????
            for (j = now;j < i + 1 ;j ++ ) {
            ????????????????
            int ?t = Search(arr[j].y);
            ????????????????root[j]
            = t;pre[j + 1 ] = num[t - 1 ].x;
            ????????????????
            if (max_sum < t) {
            ????????????????????max_sum
            = t;best_road = j + 1 ;????
            ????????????????}
            ????
            ????????????}

            ????????????
            for (j = now;j < i + 1 ;j ++ ) {
            ????????????????
            if (root[j] == top) {
            ????????????????????num[top].x
            = j + 1 ;
            ????????????????????num[top
            ++ ].y = arr[j].y;????
            ????????????????}

            ????????????????
            else ? if (arr[j].y < num[root[j]].y) {
            ????????????????????num[root[j]].x
            = j + 1 ;
            ????????????????????num[root[j]].y
            = arr[j].y;????
            ????????????????}
            ????
            ????????????}

            ????????}

            ????????OK
            = false ;
            ????????printf(
            " %d\n " ,max_sum);
            ????????PRINT(best_road);printf(
            " \n " );
            ????}

            }

            posted on 2009-05-10 22:43 KNIGHT 閱讀(138) 評論(1)  編輯 收藏 引用

            FeedBack:
            # re: Beautiful People
            2009-05-10 22:47 | Knignt
            額 上面復(fù)制的時候搞錯了一句話 自己加到循環(huán)里面就可以了
            從0到n的循環(huán)開始的時候加上
            for(now=i,j=i+1;j<n&&arr[j].x==arr[i].x;i=j,j++);
            用了二分的思想
              回復(fù)  更多評論
              
            <2009年3月>
            22232425262728
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久久久青草线蕉综合超碰| 国产成人综合久久综合| 日韩久久无码免费毛片软件| 久久久久97国产精华液好用吗| 欧美成a人片免费看久久| 亚洲欧美国产日韩综合久久| 亚洲国产精品无码久久久蜜芽| 久久精品无码午夜福利理论片 | 人妻精品久久久久中文字幕69 | 久久精品亚洲福利| 久久久亚洲欧洲日产国码是AV | 国产精品99久久免费观看| 99久久精品九九亚洲精品| 青青青青久久精品国产h久久精品五福影院1421 | 精品多毛少妇人妻AV免费久久| 思思久久精品在热线热| 久久99热精品| 中文字幕久久亚洲一区| 青青草原综合久久| 久久人做人爽一区二区三区| 久久精品国产亚洲一区二区| 精品久久久久久无码不卡| 国产91久久综合| 国产婷婷成人久久Av免费高清| 久久笫一福利免费导航| 国产精品免费久久久久影院 | 精品熟女少妇a∨免费久久| 日本精品一区二区久久久| 久久久久四虎国产精品| 久久人人妻人人爽人人爽| 久久99热这里只有精品66| 国产精品日韩深夜福利久久| 国产精品久久自在自线观看| 激情伊人五月天久久综合| 久久99精品久久久大学生| 香蕉久久夜色精品国产2020| 久久免费99精品国产自在现线| 精品人妻伦九区久久AAA片69 | 久久久久久国产精品无码超碰| 午夜久久久久久禁播电影| 久久久婷婷五月亚洲97号色|