首页 > 代码库 > 线段树---HDU1394Minimum Inversion Number
线段树---HDU1394Minimum Inversion Number
此题和上题略有不同，但是大体差不多，不过要把题意转换过来，题目大体意思为， 输入n， 也就是n个数，这些数为0 - (n-1)， 这些数刚开始给定输入的顺序， 然后求他的逆序数，然后接着把第一个移到这个数列的末尾，这时候再求出一个逆序数，直到移动一个周期，也就是移动了n次， 求他们之中的最小的一个逆序数。
大体思路：
1. 首先建立线段树，初始化每个节点的值都为0
2. 输入原序列的同时，将原序列的逆序数求出来
其中这个求的过程为找到它导致的逆序数为多少，就是找在它之前有多少个比它大的
3. 遍历一遍， 然后将剩下的n - 1 个序列的逆序数求出来，其中这里有个公式， 可以推导出来，就是可以这么考虑，假设这是第一次将第一个数移到数组的末尾，假设这个数为X[i], 它所导致的 整个数组的逆序数的变化为: 首先，它造成他后面数的逆序数为X[i](这里的X[i]就是它本身), 这个是当前数组中把它去掉之后减少的逆序数， 所以去掉它之后整个数组的逆序数就是 Sum - x[i](这里Sum就是总的逆序数)， 然后把它加到最后，它可以增加的逆序数就为 n - 1 - x[i], 所以变化这一次当前数组的逆序数为 Sum - x[i] + n - 1 - x[i]; 这个可以这么求公式，是因 为这个题特殊， 因为数组里面的数为从0 - n-1， 而且还没有重复的。
下面是代码的实现：
1 #include <cstdio> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int MAX = 5010 * 4; 7 int sum[MAX]; 8 //更新跟其有关的以上所有节点 9 void pushUp(int root)10 {11 sum[root] = sum[root * 2] + sum[root * 2 + 1];12 }13 14 void buildTree(int root, int left, int right)15 {16 sum[root] = 0;//初始化 17 if(left == right)18 {19 return;20 }21 int mid = (left + right) / 2;22 buildTree(root * 2, left, mid);23 buildTree(root * 2 + 1, mid + 1, right);24 //pushUp(root);//这里可以不需要， 因为初始化都是0 25 }26 27 void update(int root, int pos, int left, int right)28 {29 if(left == right)30 {31 sum[root]++;32 return;33 }34 int mid = (left + right) / 2;35 if(pos <= mid)36 update(root * 2, pos, left, mid);37 else38 update(root * 2 + 1, pos, mid + 1, right);39 pushUp(root);40 }41 //L， R代表要寻找的区间， left和right代表当前区间 42 int getSum(int root, int L, int R, int left, int right)43 {44 /*找大于L的， 因为大于L才能导致逆序数， 所以找它之前所有大于L的，45 即在线段上区间可以这么写 */46 if(L <= left && R >= right)47 {48 return sum[root];49 }50 int mid = (left + right) / 2;51 int res = 0;52 if(L <= mid)53 {54 res += getSum(root * 2, L, R, left, mid);55 }56 if(R > mid)57 {58 res += getSum(root * 2 + 1, L, R, mid + 1, right);59 }60 return res;61 }62 63 int main()64 {65 int x[MAX];66 int n;67 while(~scanf("%d", &n))68 {69 buildTree(1, 0, n - 1);70 int Sum = 0;71 for(int i = 0; i < n; i++)72 {73 scanf("%d", &x[i]);74 //获得当前数导致的逆序数 75 Sum += getSum(1, x[i], n - 1, 0, n - 1);76 update(1, x[i], 0, n - 1);77 }78 int t = Sum;79 for(int i = 0; i < n; i++)80 {81 //此公式是由 Sum = Sum - x[i] + n - 1 - x[i]的变形 82 Sum += n - x[i] - x[i] - 1;83 t = min(Sum, t);84 }85 printf("%d\n", t);86 }87 88 return 0;89 }
线段树---HDU1394Minimum Inversion Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。