首页 > 代码库 > poj 1084 Brainman
poj 1084 Brainman
题目链接：http://poj.org/problem?id=1804
思路：
序列的逆序数即为交换次数，所以求出该序列的逆序数即可。
根据分治法思想，序列分为两个大小相等的两部分，分别求子序列的逆序数；对于右子序列中的每一个数，求出左序列中大于它的数的数目，计算的和即为解。
另外，使用Merge排序时，可以很容易求得对于右子序列中的每一个数，左序列中大于它的数的数目。
代码：
#include <stdio.h>#include <limits.h>long long Count = 0;const int MAX_N = 1000 + 10;long long A[MAX_N], L[MAX_N], R[MAX_N];void Merge(long long A[], int p, int q, int r){ int i, j, k; int n1 = q - p + 1; int n2 = r - q; for (int i = 0; i < n1; ++i) L[i] = A[p + i]; for (int j = 0; j < n2; ++j) R[j] = A[q + j + 1]; i = j = 0; k = p; L[n1] = INT_MAX; R[n2] = INT_MAX; while (k <= r) { if (L[i] > R[j]) { A[k++] = R[j++]; Count += n1 - i; } else A[k++] = L[i++]; }}void Merge_Sort(long long A[], int p, int q){ int r = (p + q) / 2; if (p < q) { Merge_Sort(A, p, r); Merge_Sort(A, r + 1, q); Merge(A, p, r, q); }}int main(){ int n; int Scenario = 0; scanf("%d", &n); for (int i = 0; i < n; ++i) { int Num; scanf("%d", &Num); Count = 0; Scenario++; for (int i = 0; i < Num; ++i) scanf("%lld ", &A[i]); Merge_Sort(A, 0, Num - 1); printf("Scenario #%d:\n%lld\n\n", Scenario, Count); } return 0;}
poj 1084 Brainman
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。