Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴个程序,需要者就看下,否则请无视!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator