题目链接
http://poj.org/problem?id=2299
题意 给出一个序列 求出 这个序列要排成有序序列 至少要经过多少次交换
思路
求逆序对的过程 但是因为数据范围比较大 到 999999999 但是 给的 n 的数量又比较少 所以 离散化一下就可以了
比如 给出的
9 1 0 5 4原始ID 0 1 2 3 4
排序后 0 1 4 5 9 原始ID 2 1 4 3 0
然后就可以发现 求 9 1 0 5 4 的 所有逆序对个数 实际和 求 2 1 4 3 0 的逆序对个数 是一样的
然后 我们就可以将数据范围缩小到 50000
就可以用数组保存了
因为 sum 求得的是 之前比当前数字小的数字的个数 那么 逆序对个数就是 i - sum(i)
然后套用树状数组就可以了
参考 https://www.cnblogs.com/George1994/p/7710886.html
有一个坑点是 要用long long
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 5e5 + 5; const int MOD = 1e9 + 7; int a[maxn]; int sum[maxn]; struct node { int v, ord; }q[maxn]; bool comp(node x, node y) { return x.v < y.v; } int lowbit(int x) { return x & (-x); } int Sum(int n) { int ans = 0; while (n > 0) { ans += a[n]; n -= lowbit(n); } return ans; } void add(int x) { while (x <= maxn) { a[x]++; x += lowbit(x); } } int main() { int n; while (scanf("%d", &n) && n) { CLR(a, 0); CLR(q, 0); CLR(sum, 0); for (int i = 0; i < n; i++) { scanf("%d", &q[i].v); q[i].ord = i; } sort(q, q + n, comp); ll ans = 0; for (int i = 0; i < n; i++) { ans += (i) - Sum(++q[i].ord); add(q[i].ord); } cout << ans << endl; } }转载于:https://www.cnblogs.com/Dup4/p/9433124.html
