HDU 1394 Minimum Inversion Number(树状数组||线段树)

最后更新于:2022-04-01 15:53:04

题目链接:[点击打开链接](http://acm.hdu.edu.cn/showproblem.php?pid=1394) 对于求逆序数的问题, 通常用线段树或者树状数组来维护, 树状数组代码短,好写, 还是尽量写树状数组吧。 首先求出原始排列的逆序数,  那么对于每一次操作, 因为都是将当前排列的第一个数拿到最后一个位置, 所以答案就增加了所有比他大的数字个数,减小了所有比他小的数字个数。 细节参见代码: ~~~ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; typedef long long ll; const double PI = acos(-1.0); const double eps = 1e-6; const int INF = 1000000000; const int maxn = 5000+10; int T,n,m,bit[maxn],a[maxn]; int sum(int x) { int ans = 0; while(x > 0) { ans += bit[x]; x -= x & -x; } return ans; } void add(int x, int d) { while(x <= n) { bit[x] += d; x += x & -x; } } int main() { while(~scanf("%d",&n)) { memset(bit, 0, sizeof(bit)); int ans = 0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]++; ans += sum(n) - sum(a[i]); add(a[i], 1); } int cur = ans; for(int i=1;i<n;i++) { int cnt = sum(a[i]-1); cur += n - 1 - cnt - cnt; ans = min(ans, cur); } printf("%d\n",ans); } return 0; } ~~~
';