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

            Why so serious? --[NKU]schindlerlee

            2010年02月08日星期一.sgu180 && pku2299 歸并排序求逆序對

            2010年02月08日星期一.sgu180 歸并排序求逆序對
            歸并排序求逆序對
            舉例說明:
            在歸并排序合并兩個有序鏈時
            i為第一鏈的指針,j為第二個的
            以下部分需要等寬字體才能正確查看
            1 4 5 9

            2 4 7 7

            i++
            ---------
              * * *
            1 4 5 9
              ↑
            2 4 7 7

            j++,res += 3
            ---------
            1 4 5 9
              ↑
            2 4 7 7
              ↑
            i++
            ---------
                * *
            1 4 5 9
                ↑
            2 4 7 7
              ↑
            j++,res += 2
            ---------
            1 4 5 9
                ↑
            2 4 7 7
                ↑
            i++
            ---------
                  *
            1 4 5 9
                  ↑
            2 4 7 7
                ↑
            j++,res += 1
            ---------
                  *
            1 4 5 9
                  ↑
            2 4 7 7
                  ↑
            j++,res += 1
            ---------
            1 4 5 9
                  ↑
            2 4 7 7
                    ↑
            ---------
            之后將兩個鏈中沒處理完的添加到buf中


             1 
             2 const int N = 65600;
             3 int n,a[N],buf[N];
             4 LL res;
             5 
             6 void mergesort(int beg,int end)
             7 {
             8   if (end <= beg + 1) {
             9       if (a[beg] > a[end]) {
            10           res ++;
            11           swap(a[beg],a[end]);
            12       }
            13       return;
            14   }
            15   int mid = (beg + end)/2,i,j,k;
            16   mergesort(beg,mid);
            17   mergesort(mid+1,end);
            18   for (i = beg,j = mid + 1,k = beg;i <= mid && j <= end;) {
            19       if (a[i] > a[j]) {
            20           res += mid + 1 - i;
            21           buf[k++= a[j++];
            22       }else if (a[i] <= a[j]) {
            23           buf[k++= a[i++];
            24       }
            25   }
            26   while (i <= mid) { buf[k++= a[i++]; }
            27   while (j <= end) { buf[k++= a[j++]; }
            28   for (i = beg;i <= end;i++) { a[i] = buf[i]; }
            29 }
            30 
            31 int main()
            32 {
            33   int i,j,k;
            34   scanf("%d",&n);
            35   for (i = 0;i < n;i++) {
            36       scanf("%d",a + i);
            37   }
            38   mergesort(0,n-1);
            39   cout << res << endl;
            40   //printf("%d\n",res);
            41   return 0;
            42 



            posted on 2010-02-08 23:54 schindlerlee 閱讀(1188) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告

            久久96国产精品久久久| 亚洲午夜无码久久久久小说| 综合网日日天干夜夜久久| 亚洲中文久久精品无码ww16 | 亚洲午夜久久久久妓女影院| 久久久久久国产精品无码下载| 日韩精品久久无码人妻中文字幕| 国产精品久久亚洲不卡动漫| 青春久久| 国产成人久久精品激情| 久久精品成人| 日本道色综合久久影院| 久久久久久精品成人免费图片| 国产精品亚洲美女久久久| 国产A三级久久精品| 久久国产综合精品五月天| av无码久久久久不卡免费网站 | 久久综合噜噜激激的五月天| 国产叼嘿久久精品久久| 熟妇人妻久久中文字幕| 亚州日韩精品专区久久久| 国产精品99久久精品| 亚洲午夜久久久久妓女影院| 亚洲国产成人久久笫一页| 岛国搬运www久久| 久久99久久99小草精品免视看 | 亚洲国产成人久久笫一页| 大香网伊人久久综合网2020| 国产午夜福利精品久久2021 | 欧洲精品久久久av无码电影| 一本色道久久88综合日韩精品 | 伊色综合久久之综合久久| 丁香五月综合久久激情| 久久综合久久综合九色| 国产精品激情综合久久| 狠狠色丁香久久综合五月| 精品久久香蕉国产线看观看亚洲| 99久久这里只有精品| 久久综合丁香激情久久| 国产精品欧美久久久久无广告| 2020最新久久久视精品爱|