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

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            POJ 2188 Cow Laundry---求逆序數

            Posted on 2010-01-30 03:07 Uriel 閱讀(633) 評論(0)  編輯 收藏 引用 所屬分類: POJ
                跟著隊長切的題,以為可以迅速的水過去。。誰知看完暈乎暈乎的,題意都不懂。。一翻Discuss說是逆序數,完全沒想法。。想來想去怎么套上逆序數的東西。。基本上已經是湊答案了。。
                WA了幾次之后終于猜對題意了。。
                由于不一定編號要排好,只要最后對應就行,所以第一步就是改編號,其中一個改為按順序的1-N,另一個改為與之對應的編號,求其逆序數即可,我的丑陋代碼。求逆序數用mergeSort,以前做2299寫的,做模板用了~
            /*Problem: 2188  User: Uriel 
               Memory: 180K  Time: 16MS 
               Language: C++  Result: Accepted
            */
             

            #include
            <stdio.h>
            #include
            <stdlib.h>
            #include
            <algorithm>
            using namespace std;

            int b[1010],N,change,a[1010],flag[1010],c[1010];

            void merge(int p,int q,int r)
            {
                
            int i,j=0;
                
            int beginA=p,endA=q,beginB=q+1,endB=r; 
                
            while(beginA<=endA && beginB<=endB) 
                
            {
                    
            if(a[beginA]<=a[beginB]) 
                    
            {
                        b[j
            ++]=a[beginA++];
                    }
             
                   
            else 
                   
            {
                        b[j
            ++]=a[beginB++];
                        change 
            += q - beginA + 1;
                   }

                }

                
            while(beginA<=endA) 
                
            {
                    b[j
            ++]=a[beginA++];
                }

                
            while(beginB<=endB) 
                
            {
                    b[j
            ++]=a[beginB++];
                }

                
            for(i=0;i<j;i++)
                
            {
                    a[p
            +i]=b[i];
                }

            }


            void mergeSort(int first, int last)
            {
                
            int mid;
                
            if(first<last)
                
            {
                    mid
            =(first+last)/2;
                    mergeSort(first,mid);
                    mergeSort(mid
            +1,last);
                    merge(first,mid,last);
                }

            }


            int main()
            {
                
            int i,x,y;
                scanf(
            "%d",&N);
                
            for(i=0;i<N;i++)
                
            {
                    scanf(
            "%d %d",&a[i],&c[i]);
                    flag[c[i]]
            =i;
                }

                
            for(i=0;i<N;i++)
                
            {
                    a[i]
            =flag[a[i]];
                }

                change
            =0;
                mergeSort(
            0,N-1);
                printf(
            "%d\n",change);
                system(
            "PAUSE");
                
            return 0;
            }

            久久AⅤ人妻少妇嫩草影院| 亚洲精品乱码久久久久久中文字幕 | 超级碰碰碰碰97久久久久| 久久国产成人| 性做久久久久久久| 99久久精品免费| 中文字幕无码免费久久| 久久国产免费观看精品| 天天综合久久一二三区| 久久精品国产第一区二区三区| 久久婷婷久久一区二区三区| 久久人人爽人人爽人人片AV不| www.久久热| 免费精品久久天干天干| 久久996热精品xxxx| 久久国产欧美日韩精品| 久久久久久精品成人免费图片| 亚洲精品高清久久| 日韩乱码人妻无码中文字幕久久 | 久久久无码精品亚洲日韩按摩| 国产午夜精品久久久久九九电影| 国色天香久久久久久久小说| 久久亚洲AV永久无码精品| 久久电影网2021| 久久夜色精品国产欧美乱| 中文精品99久久国产| 久久综合综合久久97色| 国产三级久久久精品麻豆三级| 伊人久久大香线蕉亚洲五月天| 久久久久人妻一区精品果冻| 国产一区二区精品久久| 久久精品18| 久久精品国内一区二区三区| 漂亮人妻被黑人久久精品| 久久久亚洲AV波多野结衣| 亚洲精品第一综合99久久| 亚洲国产成人精品久久久国产成人一区二区三区综 | 久久中文字幕人妻丝袜| 青青热久久国产久精品| 一本色道久久88综合日韩精品| 久久久久国色AV免费观看|