亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

SZU:B85 Alec's Eggs

系統(tǒng) 1844 0

Description

Eggs

Alec has a lot of eggs. One day, he want to sort them in a ascending sequence by weight. But he only can switch two eggs which are adjoining by each other because he has two hands only. Now he ask for your help, and you are enthusiastic. You decide help him calculate the total numbers of switch he need at least.

Attention: the weight of each egg less than 100,000,000 units.

Input

There are multiply test case.The first line describe the number of test case?. For each test case, the first line describe the number of eggs that Alec has,?. The second line describe the weight of each eggs splited by a space.

Output

Output the total number of switch that Alec need at least. One line for each test case. The total number may be very very large but fited in 64-bit integer.

Sample Input

    
      2

2

2 1

2

2 3


    
  

Sample Output

    
      1

0
      




題意:

題意:將相鄰的兩個元素進行排序,用到二路歸并算法,

貼上代碼:

?

      
         1
      
       #include <stdio.h>


      
         2
      
       #include <stdlib.h>


      
         3
      
      
         4
      
      
        #define
      
       MAX 100001


      
         5
      
      
         6
      
      
        int
      
      
         n, a[MAX], t[MAX];


      
      
         7
      
      
        long
      
      
        long
      
      
         sum;


      
      
         8
      
      
         9
      
      
        /*
      
      
         歸并 
      
      
        */
      
      
        10
      
      
        void
      
       Merge(
      
        int
      
       l, 
      
        int
      
       m, 
      
        int
      
      
         r)


      
      
        11
      
      
        {


      
      
        12
      
      
        /*
      
      
         p指向輸出區(qū)間 
      
      
        */
      
      
        13
      
      
        int
      
       p = 
      
        0
      
      
        ;


      
      
        14
      
      
        /*
      
      
         i、j指向2個輸入?yún)^(qū)間 
      
      
        */
      
      
        15
      
      
        int
      
       i = l, j = m + 
      
        1
      
      
        ;


      
      
        16
      
      
        /*
      
      
         2個輸入?yún)^(qū)間都不為空時 
      
      
        */
      
      
        17
      
      
        while
      
      (i <= m && j <=
      
         r)


      
      
        18
      
      
            {


      
      
        19
      
      
        /*
      
      
         取關(guān)鍵字小的記錄轉(zhuǎn)移至輸出區(qū)間 
      
      
        */
      
      
        20
      
      
        if
      
       (a[i] >
      
         a[j])


      
      
        21
      
      
                {


      
      
        22
      
                   t[p++] = a[j++
      
        ];


      
      
        23
      
      
        /*
      
      
         a[i]后面的數(shù)字對于a[j]都是逆序的 
      
      
        */
      
      
        24
      
                   sum += m - i + 
      
        1
      
      
        ;


      
      
        25
      
      
                }


      
      
        26
      
      
        else
      
      
        27
      
      
                {


      
      
        28
      
                   t[p++] = a[i++
      
        ];


      
      
        29
      
      
                }


      
      
        30
      
      
            }


      
      
        31
      
      
        /*
      
      
         將非空的輸入?yún)^(qū)間轉(zhuǎn)移至輸出區(qū)間 
      
      
        */
      
      
        32
      
      
        while
      
      (i <= m) t[p++] = a[i++
      
        ];


      
      
        33
      
      
        while
      
      (j <= r) t[p++] = a[j++
      
        ];


      
      
        34
      
      
        /*
      
      
         歸并完成后將結(jié)果復制到原輸入數(shù)組 
      
      
        */
      
      
        35
      
      
        for
      
       (i = 
      
        0
      
      ; i < p; i++
      
        )


      
      
        36
      
      
            {


      
      
        37
      
               a[l + i] =
      
         t[i];


      
      
        38
      
      
            }


      
      
        39
      
      
        }


      
      
        40
      
      
        41
      
      
        /*
      
      
         歸并排序 
      
      
        */
      
      
        42
      
      
        void
      
       MergeSort(
      
        int
      
       l, 
      
        int
      
      
         r)


      
      
        43
      
      
        {


      
      
        44
      
      
        int
      
      
         m;


      
      
        45
      
      
        if
      
       (l <
      
         r)


      
      
        46
      
      
            {


      
      
        47
      
      
        /*
      
      
         將長度為n的輸入序列分成兩個長度為n/2的子序列 
      
      
        */
      
      
        48
      
               m = (l + r) / 
      
        2
      
      
        ;


      
      
        49
      
      
        /*
      
      
         對兩個子序列分別進行歸并排序 
      
      
        */
      
      
        50
      
      
                MergeSort(l, m);


      
      
        51
      
               MergeSort(m + 
      
        1
      
      
        , r);


      
      
        52
      
      
        /*
      
      
         將2個排好的子序列合并成最終有序序列 
      
      
        */
      
      
        53
      
      
                Merge(l, m, r);


      
      
        54
      
      
            }


      
      
        55
      
      
        }


      
      
        56
      
      
        57
      
      
        int
      
      
         main()


      
      
        58
      
      
        {


      
      
        59
      
      
        int
      
      
         i;


      
      
        60
      
      
        int
      
      
         t;


      
      
        61
      
           scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        t);


      
      
        62
      
      
        while
      
      (t--
      
        )


      
      
        63
      
      
            {


      
      
        64
      
               scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        n);


      
      
        65
      
      
        if
      
       (n == 
      
        0
      
      ) 
      
        break
      
      
        ;


      
      
        66
      
               sum = 
      
        0
      
      
        ;


      
      
        67
      
      
        for
      
      (i = 
      
        0
      
      ; i < n; i++
      
        )


      
      
        68
      
      
                {


      
      
        69
      
                   scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        a[i]);


      
      
        70
      
      
                }


      
      
        71
      
               MergeSort(
      
        0
      
      , n - 
      
        1
      
      
        );


      
      
        72
      
               printf(
      
        "
      
      
        %lld\n
      
      
        "
      
      
        , sum);


      
      
        73
      
      
            }


      
      
        74
      
      
        return
      
      
        0
      
      
        ;


      
      
        75
      
       }
    

?

?

上面代碼速度沒有優(yōu)化,

下面的是網(wǎng)友的代碼:

      
         1
      
       #include <stdio.h>


      
         2
      
      
        #define
      
       MAX 100000


      
         3
      
      
        int
      
      
         n,flag,a[MAX],b[MAX];


      
      
         4
      
      
        long
      
      
        long
      
      
         cnt;


      
      
         5
      
      
        void
      
       Merge(
      
        int
      
       *res,
      
        int
      
       *cop,
      
        int
      
       l,
      
        int
      
       lt,
      
        int
      
       r,
      
        int
      
      
         rt)


      
      
         6
      
      
        {


      
      
         7
      
      
        int
      
      
        base
      
      =
      
        l;


      
      
         8
      
      
        while
      
      (
      
        base
      
      <=
      
        rt)


      
      
         9
      
      
            {


      
      
        10
      
      
        while
      
      ((l<=lt && cop[l]<=cop[r]) || (l<=lt && r>rt)) res[
      
        base
      
      ++]=cop[l++
      
        ];


      
      
        11
      
      
        while
      
      ((r<=rt && cop[l]>cop[r]) || (r<=rt && l>
      
        lt))


      
      
        12
      
      
                {


      
      
        13
      
                   cnt+=lt-l+
      
        1
      
      
        ;


      
      
        14
      
                   res[
      
        base
      
      ++]=cop[r++
      
        ];


      
      
        15
      
      
                }


      
      
        16
      
      
            }


      
      
        17
      
      
        }


      
      
        18
      
      
        void
      
      
         MergeSort()


      
      
        19
      
      
        {


      
      
        20
      
      
        int
      
       step=
      
        2
      
      
        ,semi,c,s,i,l,r,lt,rt;


      
      
        21
      
      
        int
      
       *res=NULL,*cop=
      
        NULL;


      
      
        22
      
      
        while
      
      (step<
      
        2
      
      *
      
        n)


      
      
        23
      
      
            {


      
      
        24
      
               c=n/
      
        step;


      
      
        25
      
               s=n%
      
        step;


      
      
        26
      
               semi=step/
      
        2
      
      
        ;


      
      
        27
      
      
        if
      
      (s>semi) c++
      
        ;


      
      
        28
      
               flag++
      
        ;


      
      
        29
      
      
        if
      
      (flag%
      
        2
      
      
        )


      
      
        30
      
      
                {


      
      
        31
      
                   res=
      
        b;


      
      
        32
      
                   cop=
      
        a;


      
      
        33
      
      
                }


      
      
        34
      
      
        else
      
      
        35
      
      
                {


      
      
        36
      
                   res=
      
        a;


      
      
        37
      
                   cop=
      
        b;


      
      
        38
      
      
                }


      
      
        39
      
      
        for
      
      (i=
      
        0
      
      ;i<c;i++
      
        )


      
      
        40
      
      
                {


      
      
        41
      
                   l=i*
      
        step;


      
      
        42
      
                   r=l+
      
        semi;


      
      
        43
      
                   lt=r-
      
        1
      
      
        ;


      
      
        44
      
                      rt=(n-
      
        1
      
      )<(l+step-
      
        1
      
      )?(n-
      
        1
      
      ):(l+step-
      
        1
      
      );
      
        //
      
      
        邊界非整段處理
      
      
        45
      
      
                      Merge(res,cop,l,lt,r,rt);


      
      
        46
      
      
                }


      
      
        47
      
      
        if
      
      (rt<n-
      
        1
      
      
        ){


      
      
        48
      
      
        for
      
      (i=rt+
      
        1
      
      ;i<n;i++) res[i]=cop[i];
      
        //
      
      
        非常關(guān)鍵,尾部剩余有序要記得拷貝
      
      
        49
      
      
                   }


      
      
        50
      
                 step*=
      
        2
      
      
        ;


      
      
        51
      
      
            }


      
      
        52
      
      
        }


      
      
        53
      
      
        54
      
      
        int
      
      
         main()


      
      
        55
      
      
        {


      
      
        56
      
      
        int
      
      
         i;


      
      
        57
      
      
        int
      
      
         t;


      
      
        58
      
           scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        t);


      
      
        59
      
      
        while
      
      (t--
      
        ){


      
      
        60
      
               scanf(
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        n);


      
      
        61
      
      
        62
      
               flag=cnt=
      
        0
      
      
        ;


      
      
        63
      
      
        for
      
      (i=
      
        0
      
      ;i<n;i++) scanf(
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        a[i]);


      
      
        64
      
      
                    MergeSort();


      
      
        65
      
               printf(
      
        "
      
      
        %lld\n
      
      
        "
      
      
        ,cnt);


      
      
        66
      
      
        67
      
      
            }


      
      
        68
      
      
        return
      
      
        0
      
      
        ;


      
      
        69
      
       }
    

?

?另一個版本:

      
         1
      
      
        long
      
      
        long
      
       a[
      
        100004
      
      ],b[
      
        100004
      
      ];
      
        int
      
      
         N;


      
      
         2
      
      
         3
      
      
        long
      
      
        long
      
      
         total,i,j;


      
      
         4
      
      
         5
      
      
        void
      
       Mergesort(
      
        int
      
       start,
      
        int
      
      
         end)


      
      
         6
      
      
        {


      
      
         7
      
      
        if
      
      (start<
      
        end){


      
      
         8
      
      
        int
      
       i,j,mid=(start+end)/
      
        2
      
      
        ;


      
      
         9
      
      
                        Mergesort(start,mid);


      
      
        10
      
                       Mergesort(mid+
      
        1
      
      
        ,end);


      
      
        11
      
      
        int
      
       t=start;j=mid+
      
        1
      
      ;i=
      
        start;


      
      
        12
      
      
        while
      
      (i<=mid && j<=
      
        end){


      
      
        13
      
      
        if
      
       (a[i]<=
      
        a[j])


      
      
        14
      
                           b[t++]=a[i++
      
        ];


      
      
        15
      
      
        else
      
      
        {


      
      
        16
      
                            b[t++]=a[j++
      
        ];


      
      
        17
      
                            total+=mid-i+
      
        1
      
      
        ;


      
      
        18
      
      
                        }


      
      
        19
      
      
                   }


      
      
        20
      
      
        while
      
       (i<=
      
        mid)


      
      
        21
      
                     b[t++]=a[i++
      
        ];


      
      
        22
      
      
        while
      
       (j<=
      
        end)


      
      
        23
      
                  b[t++]=a[j++
      
        ];


      
      
        24
      
      
        for
      
      (i=start;i<=end;i++
      
        )


      
      
        25
      
                         a[i]=
      
        b[i];


      
      
        26
      
      
               }


      
      
        27
      
      
        }


      
      
        28
      
      
        29
      
      
        30
      
      
        int
      
      
         main()


      
      
        31
      
      
        {


      
      
        32
      
      
        int
      
      
         t;


      
      
        33
      
      
        double
      
      
         ac;


      
      
        34
      
             scanf(
      
        "
      
      
        %d
      
      
        "
      
      , &
      
        t);


      
      
        35
      
      
        while
      
       (t--
      
        ) {


      
      
        36
      
             scanf(
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        N);


      
      
        37
      
                  total=
      
        0
      
      
        ;


      
      
        38
      
      
        for
      
      (i=
      
        0
      
      ;i<N;i++
      
        )


      
      
        39
      
                          scanf(
      
        "
      
      
        %lld
      
      
        "
      
      ,&
      
        a[i]);


      
      
        40
      
                      Mergesort(
      
        0
      
      ,N-
      
        1
      
      
        );


      
      
        41
      
                        ac = (total+N)/(N*
      
        1.0
      
      
        );


      
      
        42
      
                  printf(
      
        "
      
      
        %.2f\n
      
      
        "
      
      
        ,ac);


      
      
        43
      
      
        44
      
      
             }


      
      
        45
      
       }
    

?

?

SZU:B85 Alec's Eggs


更多文章、技術(shù)交流、商務合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: www.日日操| 亚洲国产视频在线观看 | 福利免费视频 | 一区二区视频在线播放 | 久草在线免费播放 | 伊人不卡久久大香线蕉综合影院 | 毛片视频大全 | 精品一区二区三区视频在线观看免 | 性做久久久久免费看 | 91视频免费观看高清观看完整 | 亚洲精品人成无码中文毛片 | 久草在线在线视频 | 狠狠色伊人亚洲综合成人 | 国产成人亚洲精品老王 | a级无毛片 | 在线观看香蕉免费啪在线观看 | 欧美日韩在线播一区二区三区 | 日韩成人免费在线视频 | 中文字幕在线日本 | 亚洲偷图色综合色就色 | 国产午夜精品福利 | 成人免费午间影院在线观看 | 成 人国产在线观看高清不卡 | 国产视频自拍一区 | 免费一级黄色片 | 久久黄色小视频 | 亚洲精品一区二区观看 | 欧美一级在线免费观看 | 亚洲精品一区二区在线播放 | 免费爽视频 | 国产福利福利视频 | 激情五月综合婷婷 | 欧美性猛交xx乱大交 | 小明看看成人免费 | 久久久成人网 | 亚洲欧美一区二区三区在饯 | 国产精品999在线 | 亚洲国产一区二区三区 | 国产日韩精品一区在线观看播放 | 免费看欧美理论片在线 | 九九看片 |