BNU 4208 Bubble sort (想法題)

http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=4208

注意題目是讓求趟數，是以比較原序列與排序後序列中位置相差最大的就是答案。

PS：也可以用反序表來思考。參見《計算機程式設計藝術》第三卷5.1.1

完整代碼：

/*136ms,1408KB*/

#include<cstdio>
#include<algorithm>
using namespace std;

int a[10005], Map[10005];

int main()
{
	int n, t, i, maxn;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		for (i = 0; i < n; ++i)
		{
			scanf("%d", &a[i]);
			Map[a[i]] = i;
		}
		sort(a, a + n);
		maxn = 0;
		for (i = 0; i < n; ++i)
			maxn = max(maxn, Map[a[i]] - i);
		printf("%d\n", maxn);
	}
	return 0;
}