BNU 4208 Bubble sort:想法题

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\n", maxn);
26.    }
27.    return 0;
28.}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索scanf
， map
， int
， include
， sort
， 序列
pat acm题
gb4208、gb4208 2008、tsds 42081、gb4208 2008标准下载、cirrus logic cs4208，以便于您获取更多的相关知识。