• <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>

            2182 Lost Cows

            Lost Cows

            Time Limit: 1000MS Memory Limit: 65536K
            Total Submissions: 2824 Accepted: 1742

            Description

            N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

            Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

            Given this data, tell FJ the exact ordering of the cows.

            Input

            * Line 1: A single integer, N

            * Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

            Output

            * Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

            Sample Input

            5
            1
            2
            1
            0
            

            Sample Output

            2
            4
            5
            3
            1
            

            Source



            Analysis

            Which number can we determine at the first glance of the input data? Of course, the answer is the tail. Suppose the last number of the input data, which is the number of cows with lower brand number than it, is a[n]. According to the defination, the last cow gets the (a[n]+1)th number, since there are a[n] brand number before. What's more, the brand number is constrained in range from 1 to n, so the last number is well ensured.

            Later, the earlier one will be determined in a set containing the numbers range from 1 to n except b[n], which is the brand number of the last cow. Obviously, the brand number is the (a[n-1]+1)th number in the set. The problem turns to be the method to save and search used numbers. If we create a constantly array, the cost of time in deleting and searching is both O(n) and the whole cost is o(n^2). Just consider about the segment tree. Create a segment tree of range [1,n], and the number of tree[p] is the number of brands used. When a number is inserting, calculate the remaining number of the left range: m-l+1-tree[p]. If it is larger than the current number, which is a[i]+1, then searching the left child. Otherwise, search the right one. When it is searching, adding the current root since it is clear to see that a new member is coming now. At last, when the search comes to an end and find a leave, record the range number.

            My code:

            #include <stdio.h>
            #include 
            <stdlib.h>
            #include 
            <memory.h>
            #define MAX 8000

            int main(){
                
            int n,i;
                
            int a[MAX],b[MAX];
                
            int tree[4*MAX+1];
                scanf(
            "%d",&n);
                a[
            0]=0;
                
            for (i=1;i<n;i++)
                    scanf(
            "%d",a+i);
                
            for (i=n-1;i>=0;i--){
                    
            int l,r,p,m,no;
                    no
            =a[i]+1;
                    l
            =1;r=n;p=1;
                    
            while (l<r){
                        tree[p]
            ++;
                        m
            =(l+r)>>1;
                        
            if (m-l+1-tree[2*p]>=no ){
                            r
            =m;
                            p
            <<=1;
                        }

                        
            else {
                            no
            -=m-l+1-tree[2*p];
                            l
            =m+1;
                            p
            =2*p+1;                
                        }

                    }

                    tree[p]
            ++;
                    b[i]
            =l;
                }

                
            for (i=0;i<n;i++)
                    printf(
            "%d\n",b[i]);
                
            return 0;
            }

            posted on 2008-11-22 20:36 幻浪天空領(lǐng)主 閱讀(845) 評論(0)  編輯 收藏 引用 所屬分類: POJ


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


            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久久WWW成人免费精品| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久精品亚洲AV久久久无码| 久久久无码精品亚洲日韩软件| 久久综合久久伊人| 亚洲国产另类久久久精品小说| 久久香蕉一级毛片| 亚洲综合伊人久久大杳蕉| 青青国产成人久久91网| 久久久精品人妻一区二区三区蜜桃| 久久av无码专区亚洲av桃花岛| 国产一区二区精品久久凹凸| 久久精品aⅴ无码中文字字幕重口 久久精品a亚洲国产v高清不卡 | 久久99中文字幕久久| 麻豆av久久av盛宴av| segui久久国产精品| 国产精品一区二区久久不卡| 伊人久久国产免费观看视频| 久久久WWW成人免费精品| 成人国内精品久久久久一区| 亚洲国产精品高清久久久| 久久精品视屏| 久久精品女人天堂AV麻| 久久国产精品成人免费 | 狠狠人妻久久久久久综合蜜桃| 久久99精品久久久久久久久久 | 久久天天躁狠狠躁夜夜2020老熟妇| 久久夜色精品国产噜噜麻豆 | 久久亚洲精品中文字幕| 亚洲精品午夜国产va久久| 欧美激情精品久久久久久久| 久久久久国产成人精品亚洲午夜| 国产精品久久久久久搜索| 91精品国产综合久久婷婷| 精品久久久久久| 久久99中文字幕久久| 91久久成人免费| 久久久久99精品成人片三人毛片| 久久无码一区二区三区少妇| 亚洲精品无码久久久| 久久午夜福利无码1000合集|