本文共 1962 字,大约阅读时间需要 6 分钟。
先收藏起来,改日在自己写一篇。 nyoj322Sort 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描述 You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need. For example, 1 2 3 5 4, we only need one operation : swap 5 and 4. 输入 The input consists of T number of test cases.(<0T<1000) Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n. 输出 For each case, output the minimum times need to sort it in ascending order on a single line. 样例输入 2 3 1 2 3 4 4 3 2 1 样例输出 0 6
//归并排序//http://blog.csdn.net/yuehailin/article/details/68961304 #include#include using namespace std;void mergeArray(int number[], int first, int mid, int last, int temp[]);void mergeSort(int number[], int first, int last, int temp[]);int count;int main() { int t, n, number[1005], temp[1005]; scanf("%d", &t); while (t--) { count = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &number[i]); mergeSort(number, 0, n-1, temp);// for (int i = 0; i < n; i++) printf("%d ", number[i]);// printf("\n"); printf("%d\n", count); } return 0;}void mergeArray(int number[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int position = 0; while (i <= mid && j <= last) { if (number[i] <= number[j]) { temp[position++] = number[i++]; }else { count += mid - i + 1; temp[position++] = number[j++]; } } while (i <= mid) temp[position++] = number[i++]; while (j <= last) temp[position++] = number[j++]; for (i = 0; i < position; i++) number[first+i] = temp[i];}void mergeSort(int number[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergeSort(number, first, mid, temp); mergeSort(number, mid+1, last, temp); mergeArray(number, first, mid, last, temp); }}