BNU 4208 Bubble sort:想法题

BNU 4208 Bubble sort:想法题2014-07-07 synapse7 http://acm.bnu.edu.cn/bnuoj/problem_show.php？pid=4208

注意题目是让求趟数，所以比较原序列与排序后序列中位置相差最大的就是答案。

PS：也可以用反序表来思考。参见《计算机程序设计艺术》第三卷5.1.1

完整代码：

01./*136ms,1408KB*/02.03.#include<cstdio>04.#include<algorithm>05.using namespace std;06.07.int a[10005], Map[10005];08.09.int main（）10.{11.int n, t, i, maxn;12.scanf（"%d", &t）;13.while （t--）14.{15.scanf（"%d", &n）;16.for （i = 0; i < n; ++i）17.{18.scanf（"%d", &a[i]）;19.Map[a[i]] = i;20.}21.sort（a, a + n）;22.maxn = 0;23.for （i = 0; i < n; ++i）24.maxn = max（maxn, Map[a[i]] - i）;25.printf（"%d
", maxn）;26.}27.return 0;28.}