HDU-1394 Minimum Inversion Number 树状数组

本文主要是介绍HDU-1394 Minimum Inversion Number 树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出一个0到n-1的全排列，可以将第一个数字移动到最后一个，求通过任意次数移动以后最小的逆序对数。

用树状数组求出初始状态的逆序对数，然后循环更新。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int c[5002];
int d[5002];
int n;
int update(int u) {while(u <= n) {c[u]++;u += u & -u;}return 0;
}
int query(int u) {int ans = 0;while(u) {ans += c[u];u -= u & -u;}return ans;
}
int main() {int i, j;while(~scanf("%d", &n)) {for(i = 0; i < n; i++)scanf("%d", &d[i]);memset(c, 0, sizeof(c));int ans = n * n;int l = 0;for(i = 0; i < n; i++) {//求初始逆序对数update(d[i] + 1);l += i - query(d[i]);}ans = l;//循环后移跟新for(i = 0; i < n; i++) {l = l - d[i] + n - 1 - d[i];if(l < ans)ans = l;}printf("%d\n", ans);}return 0;
}

这篇关于HDU-1394 Minimum Inversion Number 树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---