首页 > 代码库 > HDU1394 线段树求最小逆序数
HDU1394 线段树求最小逆序数
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1394
求最小的逆序数，在此贴下逆序数的概念：
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列；逆序数为奇数的排列称为奇排列。如2431中，21，43，41，31是逆序，逆序数是4，为偶排列。
也是就说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。
如：0 3 4 1 2
设逆序数初始n = 0；
由于0后面没有比它小的，n = 0
3后面有1,2 n = 2
4后面有1,2,n = 2
所以该序列逆序数为 n=2+2=4
其根据题意移动产生的序列有(每次将第一个字母移到最后一个)
3 4 1 2 0 逆序数：8
4 1 2 0 3 逆序数：6
1 2 0 3 4 逆序数：2
2 0 3 4 1 逆序数：4
所以最小逆序数为2
这里有一个求最小逆序数的规律，只要知道初始序列的逆序数就能够递推比较得出最小逆序数
引用上面的例子
3 4 1 2 0 逆序数：8
4 1 2 0 3 逆序数：6
3后面比3小的数有1,2,0，所以逆序对为t=3，比3大的数只有4，所以顺序对为1，即顺序对=n-1-t,n表示序列中数字的总个数，当3移到最后一位时，逆序对转化成顺序对，
所以原来的逆序数k要减去对于该数的原来的逆序对，而顺序对转化成逆序对，所以要加上
归纳总结得到 现在的逆序数=k+(n-1-t)-t=k+n-2t-1
#include <cstdio>#include <algorithm>using namespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 5555;int sum[maxn<<2];void PushUP(int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l,int r,int rt) { sum[rt] = 0; if (l == r) return ; int m = (l + r) >> 1; build(lson); build(rson);}void update(int p,int l,int r,int rt) { if (l == r) { sum[rt] ++; return ; } int m = (l + r) >> 1; if (p <= m) update(p , lson); else update(p , rson); PushUP(rt);}int query(int L,int R,int l,int r,int rt) { if (L <= l && r <= R) { return sum[rt]; } int m = (l + r) >> 1; int ret = 0; if (L <= m) ret += query(L , R , lson); if (R > m) ret += query(L , R , rson); return ret;}int x[maxn];int main() { int n; while (~scanf("%d",&n)) { build(0 , n - 1 , 1); int sum = 0; for (int i = 0 ; i < n ; i ++) { scanf("%d",&x[i]); sum += query(x[i] , n - 1 , 0 , n - 1 , 1); update(x[i] , 0 , n - 1 , 1); } int ret = sum; for (int i = 0 ; i < n ; i ++) { sum += n - x[i] - x[i] - 1; ret = min(ret , sum); } printf("%d\n",ret); } return 0;}
HDU1394 线段树求最小逆序数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。