sdutoj 2554 冒泡排序中数据交换的次数 树状数组

缘起

日常浪费生命 sdutoj 2554 冒泡排序中数据交换的次数

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Problem Description
听说过冒泡排序么？一种很暴力的排序方法。今天我们不希望你用它来排序，而是希望你能算出从小到大冒泡排序的过程中一共进行了多少次数据交换。

Input
输入数据的第一行为一个正整数 T ，表示有 T 组测试数据。
接下来T行，每行第一个整数N, 然后有N个整数，无序。0<N <= 100

Output
输出共 T 行。
每行一个整数，代表本行数据从小到大冒泡排序所进行的交换次数。

Sample Input
3
5 1 2 3 4 5
4 5 3 7 1
2 2 1
Sample Output
0
4
1

注意，N<=100, 所以完全可以模拟冒泡的过程进行计数. 但是太low了——毕竟如果n的范围升到1w的话, 这个O(n^2)算法会卡死. 所以采用树状数组的算法. 其实这种问题如何和树状数组联系在一起，在【1】中已经说过了. 其实冒泡排序的次数就恰好是数组的逆序数. 而逆序数怎么和树状数组联系在一起在【1】中已经说过了.

本题再说一次. 首先，将数组中的元素进行离散化. 假设对 4、3、1、2四个数计算逆序数. 然后开一个哈希数组book（0表示从左至右遍历数组的元素尚未出现，1表示已经出现了）. 然后4来了, 发现sum{book[5,…]}是0. 所以逆序数增量为0. 然后3来了. 发现 sum{book[4,….]}是1（因为4已经在了）. 所以逆序数增量为 . 然后1来了, 因为sum{book[2,…]}是2（因为3和4已经来了）， 所以逆序数增量为2. 最后2来了, 发现 sum{book[3,…]}是2(因为3和4已经来了)，综上，逆序数为1+2+2=5.

所以本题其实就是要实时更新book数组（一个非0即1的数组）以及它的部分和. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
#include <string.h>
//#define LOCAL

int n, a[105],b[105],c[105]; // c是哈希数组的树状数组（但是本题哈希数组不需要列出来）

void discrete()
{
	memcpy(b,a,sizeof(a));
	sort(b+1,b+n+1);
	int res = unique(b+1,b+n+1)-b-1;
	for (int i = 1; i<=n;i++)
	{
		a[i] = lower_bound(b+1,b+res+1, a[i])-b;
	}
} // 离散化a

int lowbit(int x)
{
	return x&(-x);
}

int psum(int i) // 计算哈希数组[1,...,i]这前i项的和
{
	int ans = 0;
	while(i)
	{
		ans+=c[i];
		i-=lowbit(i);
	}
	return ans;
}

void updata(int i, int v) // book[i]增加v, 维护树状数组c
{
	while(i<=n)
	{
		c[i]+=v;
		i+=lowbit(i);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		memset(c, 0, sizeof(c));
		int ans = 0;
		scanf("%d", &n);
		for (int i = 1; i<=n;i++)
		{
			scanf("%d", a+i);
		}
		discrete();
		for (int i = 1; i<=n; i++)
		{
			ans+=psum(n)-psum(a[i]); // 计算哈希数组[a[i],...,n] 的部分和
			updata(a[i], 1); // 哈希数组的a[i]索引变成1, 然后维护树状数组c
		}
		printf("%d\n",ans);
	}
	return 0;
}

ac情况

6516610 yfs 2554 Accepted 0 ms 160 KiB g++ 1313 B 2019-09-04 10:15:32

参考

【1】https://yfsyfs.github.io/2019/06/06/%E7%A6%BB%E6%95%A3%E5%8C%96-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84-%E6%B1%82%E9%80%86%E5%BA%8F%E6%95%B0/