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