/*
求逆序数的四种方法
*/
/*
1. O(n^2) 暴力+递推 法:如果求出第一种情况的逆序列，其他的可以通过递推来搞出来，一开始是t[1],t[2],t[3]....t[N]
它的逆序列个数是N个，如果把t[1]放到t[N]后面，逆序列个数会减少t[1]个，相应会增加N-(t[1]+1)个
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAX_N = + ;
const int INF = 0x3f3f3f3f;
int a[MAX_N];
int num[MAX_N]; int main(void) //HDOJ 1394 Minimum Inversion Number
{
//freopen ("inC.txt", "r", stdin);
int n; while (~scanf ("%d", &n))
{
memset (num, , sizeof (num));
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]);
//a[n+i] = a[i];
}
int t = ; int sum = ;
for (int i=; i<=n; ++i) //先求解最初的数列逆序数
{
for (int j=i+; j<=n; ++j)
{
if (a[i] > a[j])
{
sum++;
}
}
}
//printf ("%d\n", sum);
int ans = INF;
for (int i=; i<=n; ++i) //更新sum，找最小
{
sum = sum - a[i] + (n - a[i] - ); //the next line contains a permutation of the n integers from 0 to n-1.
//printf ("%d\n", res); //从0到n-1的整数 所以这里用a[i] 读题不仔细 。。。。
ans = min (sum, ans);
}
printf ("%d\n", ans);
} return ;
}
O(n^2) 暴力+递推
/*
2. 归并算法
*/
#include <cstdio>
#include <algorithm>
using namespace std; const int MAX_N = + ;
const int INF = 0x3f3f3f3f;
int a[MAX_N];
int b[MAX_N];
int L[MAX_N/+], R[MAX_N/+];
int cnt = ; void Merge(int *a, int p, int q, int r)
{
int n1 = q - p + ;
int n2 = r - q;
int i, j; for (i=; i<=n1; ++i)
{
L[i] = a[p+i-];
}
for (j=; j<=n2; ++j)
{
R[j] = a[q+j];
}
L[n1+] = R[n2+] = INF;
i = j = ;
for (int k=p; k<=r; ++k)
{
if (L[i] <= R[j])
{
a[k] = L[i++];
}
else
{
a[k] = R[j++];
cnt += n1 - i + ;
}
}
} void MergeSort(int *a, int p, int r)
{
if (p < r)
{
int q = (p + r) / ;
MergeSort (a, p, q);
MergeSort (a, q+, r);
Merge (a, p, q, r);
}
} int main(void) //HDOJ 1394 Minimum Inversion Number
{
//freopen ("inC.txt", "r", stdin);
int n;
while (~scanf ("%d", &n) && n)
{
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]);
b[i] = a[i];
}
MergeSort (a, , n);
//printf ("%d\n", cnt);
int ans = INF;
for (int i=; i<=n; ++i) //注意a[i]已排序
{
cnt = cnt - b[i] + (n - b[i] - );
ans = min (cnt, ans);
}
printf ("%d\n", ans);
cnt = ;
} return ;
}
nlogn 归并排序
/*
3. nlogn 线段树-单点更新：更新比a[i]大的个数
*/
#include <cstdio>
#include <algorithm>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1 const int MAX_N = + ;
const int INF = 0x3f3f3f3f;
int a[MAX_N];
int sum[MAX_N << ]; void pushup(int rt)
{
sum[rt] = sum[rt << ] + sum[rt << | ];
} void build(int l, int r, int rt)
{
sum[rt] = ;
if (l == r) return ;
int m = (l + r) >> ;
build (lson);
build (rson);
} void update(int p, int l, int r, int rt)
{
if (l == r)
{
sum[rt]++; //记录次数
return ;
}
int m = (l + r) >> ;
if (p <= m)
{
update (p, lson);
}
else
update(p, rson);
pushup (rt);
} int query(int ql, int qr, int l, int r, int rt)
{
if (ql <= l && r <= qr)
{
return sum[rt];
}
int m = (l + r) >> ;
int ans = ;
if (ql <= m) ans += query (ql, qr, lson);
if (qr > m) ans += query (ql, qr, rson); return ans;
} int main(void) //HDOJ 1394 Minimum Inversion Number
{
//freopen ("inC.txt", "r", stdin);
int n;
while (~scanf ("%d", &n))
{
//memset (num, 0, sizeof (num));
build (, n-, );
int sum = ;
for (int i=; i<=n; ++i)
{
scanf ("%d", &a[i]);
sum += query (a[i], n-, , n-, );
update (a[i], , n-, );
}
int ans = sum;
for (int i=; i<=n; ++i)
{
sum = sum - a[i] + (n - a[i] - );
ans = std::min (sum, ans);
}
printf ("%d\n", ans);
} return ;
}
nlogn 线段树-单点更新
/*
4. 树状数组
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=;
int c[MAXN];
int a[MAXN];
int n; int lowbit(int x)
{
return x&(-x);
} void add(int i,int val)
{
while(i<=n)
{
c[i]+=val;
i+=lowbit(i);
}
} int sum(int i)
{
int s=;
while(i>)
{
s+=c[i];
i-=lowbit(i);
}
return s;
} int main() //HDOJ 1394 Minimum Inversion Number
{
//freopen ("inC.txt", "r", stdin);
while(scanf("%d",&n)!=EOF)
{
int ans=;
memset(c,,sizeof(c));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]++;
ans+=sum(n)-sum(a[i]);
add(a[i],);
}
int Min=ans;
for(int i=;i<=n;i++)
{
ans+=n-a[i]-(a[i]-);
if(ans<Min)Min=ans;
}
printf("%d\n",Min);
} return ;
}
树状数组