• <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
            很猥瑣的最長上升子序列,寫的很猥瑣 ,輸出為給出序列的序號,因?yàn)檫@個(gè)錯(cuò)了幾次 開始的時(shí)候二分寫錯(cuò)一直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 閱讀(140) 評論(1)  編輯 收藏 引用

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

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久午夜伦鲁片免费无码| 青青青青久久精品国产h| 久久久久久曰本AV免费免费| 亚洲国产精品一区二区三区久久| 久久中文字幕人妻丝袜| 精品国产乱码久久久久久1区2区| 日本精品久久久久中文字幕8| 国内精品久久久久久久久电影网| 国产成人精品综合久久久久| 国产A级毛片久久久精品毛片| 亚洲国产另类久久久精品黑人| 久久精品无码一区二区三区日韩| 亚洲AV日韩精品久久久久久久| 久久精品一区二区| 亚洲精品美女久久777777| 无码乱码观看精品久久| 91精品国产综合久久香蕉 | 久久精品国产乱子伦| 国产精品天天影视久久综合网| 天天综合久久一二三区| 国产精品九九久久免费视频| 97久久精品无码一区二区天美| 一日本道伊人久久综合影| 青草影院天堂男人久久| 久久国产热精品波多野结衣AV| 一本久道久久综合狠狠躁AV| 国产成人精品久久亚洲| 久久亚洲国产精品一区二区| www.久久热.com| 国产精品青草久久久久婷婷| 久久精品中文闷骚内射| 亚洲欧美成人综合久久久| 国产精品亚洲综合久久| 一级a性色生活片久久无少妇一级婬片免费放 | 久久有码中文字幕| 精品久久久久久国产牛牛app| 777米奇久久最新地址| 久久精品国产只有精品2020| 久久国产精品77777| 99国产欧美久久久精品蜜芽| 欧美一区二区精品久久|