共有回帖数 0 个
-
分治法（合并排序时计算）
把数组 a 划分为 [first, (first+last)/2)（左）、[(first+last)/2, last)（右） 两部分
[first, last) 的逆序数 = 左半部分逆序数 + 右半部分逆序数 + 两数分别出现在左、card(pair(i, j) | i∈左 且 j∈右)
#include stdio.h
#include string.h
#define N 100
int a[N], b[N], n;
int Calc(int first, int last)
{
if (first == last-1) return 0;
int mid = (first+last)/2, i = first, j = mid, k = first,
res = Calc(first, mid)+Calc(mid, last);
while (i mid && j last)
{
if (a = a[j]) b[k++] = a[i++], res += j-mid;
else b[k++] = a[j++];
}
while (i mid) b[k++] = a[i++], res += j-mid;
while (j last) b[k++] = a[j++];
memcpy(a+first, b+first, sizeof(b[0])*(last-first));
return res;
}
int main()
{
int res = 0;
scanf("%d", &n);
for (int i = 0; i n; ++i)
scanf("%d", &a);
printf("%dn", Calc(0, n));
return 0;
}
-----
线段树
对每一次输入的 t，计算以前输入的大于 t 的数的个数之和 s。∑s 即为结果
利用线段树，就能快速计算出任意的 s
输入的数的范围为 1~N（所以时间复杂度和前一种方法略有差别）
#include stdio.h
#define N 100
int a[N*2-1];
void Inc(int root, int first, int last, int x)
{
++a[root];
if (first == last-1) return;
if (x (first+last+1)/2) Inc(root*2+1, first, (first+last+1)/2, x);
else Inc(root*2+2, (first+last+1)/2, last, x);
}
int Sum(int root, int first, int last, int x)
{
if (first == last-1) return a[root];
return (x (first+last+1)/2 ? Sum(root*2+1, first, (first+last+1)/2, x) : 0)
+ Sum(root*2+2, (first+last+1)/2, last, x);
}
int main()
{
int n, res = 0;
for (scanf("%d", &n); n; --n)
{
int t;
scanf("%d", &t);
res += Sum(0, 1, N+1, t+1);
Inc(0, 1, N+1, t);
}
printf("%dn", res);
return 0;
}
-----
树状数组
类似于线段树
输入的数的范围为 1~N
#include stdio.h
#define N 100
int a[N+1];
void Inc(int x)
{
for (; x = N; x += (x^x-1)&x)
++a[x];
}
int Sum(int x)
{
int res = 0;
for (; x; x -= (x^x-1)&x)
res += a[x];
return res;
}
int main()
{
int n, res = 0;
for (scanf("%d", &n); n; --n)
{
int t;
scanf("%d", &t);
res += Sum(N-t);
Inc(N-t+1);
}
printf("%dn", res);
return 0;
}
楼主 2016-06-09 09:49 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
