• <input id="auww4"></input>
  • <input id="auww4"><acronym id="auww4"></acronym></input>
  • <input id="auww4"><u id="auww4"></u></input>
    <object id="auww4"><acronym id="auww4"></acronym></object>
    <menu id="auww4"></menu><input id="auww4"><u id="auww4"></u></input>
    <input id="auww4"><u id="auww4"></u></input>
  • F.A.Q
    Hand In Hand
    Online Acmers
    Forum | Discuss
    Statistical Charts
    Problem Archive
    Realtime Judge Status
    Authors Ranklist
     
         C/C++/Java Exams     
    ACM Steps
    Go to Job
    Contest LiveCast
    ICPC@China
    Best Coder beta
    VIP | STD Contests
    Virtual Contests
        DIY | Web-DIY beta
    Recent Contests
    Author ID 
    Password 
     Register new ID

    歸并排序代碼!

    Posted by BLBLHK at 2020-11-06 21:14:56 on Problem 1394
    (0)  


    #include <iostream>
    using namespace std;
    int ans;
    void merge(int arr[], int tempArr[], int left, int mid, int right)
    {
        int l_pos = left;
        int r_pos = mid + 1;
        int pos = left;
        while (l_pos <= mid && r_pos <= right)
        {
            if (arr[l_pos] < arr[r_pos])
                tempArr[pos++] = arr[l_pos++];
            else
            {
                tempArr[pos++] = arr[r_pos++];
                ans += mid - l_pos + 1;
            }
        }
        while (l_pos <= mid)
        {
            tempArr[pos++] = arr[l_pos++];
        }
        while (r_pos <= right)
        {
            tempArr[pos++] = arr[r_pos++];
        }
        while (left <= right)
        {
            arr[left] = tempArr[left];
            left++;
        }
    }
    void msort(int arr[], int tempArr[], int left, int right)
    {
        if (left < right)
        {
            int mid = (right + left) / 2;
            msort(arr, tempArr, left, mid);
            msort(arr, tempArr, mid + 1, right);
            merge(arr, tempArr, left, mid, right);
        }
    }
    void merge_sort(int arr[], int n)
    {
        int* tempArr = (int*)malloc(n * sizeof(int));
        if (tempArr)
        {
            msort(arr, tempArr, 0, n - 1);
            free(tempArr);
        }
        else
        {
            cout << "錯誤" << endl;
        }
    }
    int main()
    {
        int n;
        while (cin >> n)       
        {                      
            int a[5050] = { 0 };
            int u[5050] = { 0 };
            for (int i = 0; i < n; i++)
            {
                cin >> a[i];
                u[i] = a[i];
            }
            ans = 0;
            merge_sort(a, n);
            int min = ans;
            for (int i = 0; i < n; i++)
            {
                ans = ans + (n - u[i]) - u[i] - 1;
                if (min > ans)
                    min = ans;
            }
            cout << min << endl;
        }
        return 0;
    }

    Followed by:


    Post your reply here:

    Author ID
    Password
    Title
    Content  
     
    Hangzhou Dianzi University Online Judge 3.0
    Copyright © 2005-2020 HDU ACM Team. All Rights Reserved.
    Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
    Total 0.015600(s) query 5, Server time : 2020-11-09 02:27:40, Gzip enabled
    棋牌