首页 > 代码库 > HDU 1394 Minimum Inversion Number(线段树求最小逆序数对)
HDU 1394 Minimum Inversion Number(线段树求最小逆序数对)
HDU 1394 Minimum Inversion Number(线段树求最小逆序数对)
ACM
题目地址:HDU 1394 Minimum Inversion Number
题意:
给一个序列由[1,N]构成,可以通过旋转把第一个移动到最后一个。
问旋转后最小的逆序数对。
分析:
注意,序列是由[1,N]构成的,我们模拟下旋转,总的逆序数对会有规律的变化。
求出初始的逆序数对再循环一遍就行了。
至于求逆序数对,我以前用归并排序解过这道题:点这里。
不过由于数据范围是5000,所以完全可以用线段树或树状数组来做:求某个数的作为逆序数对的后面部分的对数,可以在前面的数中查询小于这个数的数的个数。
直接在线一边加一边查就行了,复杂度为O(nlogn)。
不过老实说,这题的单个数没有太大,不然线段树和树状数组都开不下的。所以求逆序数对的最佳算法应该是归并排序解。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: 1394_segment_tree.cpp * Create Date: 2014-08-05 10:08:42 * Descripton: segment tree */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) #define lson(x) ((x) << 1) #define rson(x) ((x) << 1 | 1) typedef long long ll; const int N = 5010; const int ROOT = 1; // below is sement point updated struct seg { ll w; }; struct segment_tree { seg node[N << 2]; void update(int pos) { node[pos].w = node[lson(pos)].w + node[rson(pos)].w; } void build(int l, int r, int pos) { if (l == r) { node[pos].w = 0; return; } int m = (l + r) >> 1; build(l, m, lson(pos)); build(m + 1, r, rson(pos)); update(pos); } // add the point x with y void modify(int l, int r, int pos, int x, ll y) { if (l == r) { node[pos].w += y; return; } int m = (l + r) >> 1; if (x <= m) modify(l, m, lson(pos), x, y); else modify(m + 1, r, rson(pos), x, y); update(pos); } // query the segment [x, y] ll query(int l, int r, int pos, int x, int y) { if (x <= l && r <= y) return node[pos].w; int m = (l + r) >> 1; ll res = 0; if (x <= m) res += query(l, m, lson(pos), x, y); if (y > m) res += query(m + 1, r, rson(pos), x, y); return res; } // remove the point that the sum of [0, it] is x, return its id int remove(int l, int r, int pos, ll x) { if (l == r) { node[pos].w = 0; return l; } int m = (l + r) >> 1; int res; if (x < node[lson(pos)].w) res = remove(l, m, lson(pos), x); else res = remove(m + 1, r, rson(pos), x - node[lson(pos)].w); update(pos); return res; } } sgm; int n, a[N], b[N], t, sum, mmin; int main() { while (~scanf("%d", &n)) { sgm.build(1, n, ROOT); sum = 0; repf (i, 1, n) scanf("%d", &a[i]); for (int i = n; i >= 1; i--) { b[i] = sgm.query(1, n, ROOT, 1, a[i] + 1); sum += b[i]; sgm.modify(1, n, ROOT, a[i] + 1, 1); } mmin = sum; repf (i, 1, n) { sum = sum - a[i] + (n - 1 - a[i]); mmin = min(mmin, sum); } cout << mmin << endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。