bnuoj 4208 Bubble sort

http://www.bnuoj.com/bnuoj/problem_show.php?pid=4208

【题意】：如题，求冒泡排序遍历趟数

【题解】：这题开始2B了，先模拟TLE，然后想了一下，能不能根据始末状态来得到点什么。。。

　　　　3 2 4 1

　　　　　　　　　|==> 如果开始的位置在 i 最后位置在 j ，如果 i>j 那么最少遍历次数为 i-j

1 2 3 4

【code】:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 struct Nod
 9 {
10     int a;
11     int id;
12 }node[10010];
13 
14 bool cmp(Nod a,Nod b)
15 {
16     return a.a<b.a;
17 }
18 
19 int main()
20 {
21     int t;
22     scanf("%d",&t);
23     while(t--)
24     {
25         int n;
26         scanf("%d",&n);
27         int i,j;
28         for(i=0;i<n;i++)
29         {
30             scanf("%d",&node[i].a);
31             node[i].id = i;
32         }
33         sort(node,node+n,cmp);
34         int maks = 0;
35         for(i=0;i<n;i++)
36         {
37             if(maks<node[i].id-i)
38             {
39                 maks=node[i].id-i;
40             }
41         }
42         printf("%d
",maks);
43     }
44     return 0;
45 }