Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贴个程序,需要者就看下,否则请无视!

Posted by damacheng009 at 2010-09-13 23:44:34 on Problem 2188
#include <cstdio>

const int MAX = 1001;

int tmp_arr[MAX];
int up[MAX];
int down[MAX];
int ni;

void merge(int arr[], int left, int left_end, int right, int right_end) {
    int i, j, k;
    for(i = left, j = right, k = 0; i <= left_end && j <= right_end; ++k) {
        if(arr[i] < arr[j]) {
            tmp_arr[k] = arr[i++];
        } else {
            ni += left_end - i + 1;
            tmp_arr[k] = arr[j++];
        }
    }

    if(i <= left_end) {
        for(; i <= left_end; ++i, ++k) {
            tmp_arr[k] = arr[i];
        }
    }

    if(j <= right_end) {
        for(; j <= right_end; ++j, ++k) {
            tmp_arr[k] = arr[j];
        }
    }

    for(i = 0, j = left; i < k; ++i, ++j) {
        arr[j] = tmp_arr[i];
    }
}

void merge_sort(int arr[], int left, int right) {
    if(left >= right) {
        return;
    }

    if(left + 1 == right) {
        if(arr[left] > arr[right]) {
            ++ni;
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            return;
        }
    }

    int mid = (left + right) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    merge(arr, left, mid, mid + 1, right);
}

int main() {
    //freopen("e:/data.txt", "r", stdin);
    int slot_num;
    scanf("%d", &slot_num);
    for(int i = 1; i <= slot_num; ++i) {
        scanf("%d %d", &up[i], &down[i]);
    }

    for(int i = 1; i <= slot_num; ++i) {
        for(int j = 1; j <= slot_num; ++j) {
            if(up[i] == down[j]) {
                up[i] = j;
                break;
            }
        }
    }

    ni = 0;

    merge_sort(up, 1, slot_num);

    printf("%d\n", ni);

    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator