+关注继续查看

# Sort it

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4672    Accepted Submission(s): 3244

Problem Description
You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.

Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.

Output
For each case, output the minimum times need to sort it in ascending order on a single line.

Sample Input
3
1 2 3
4
4 3 2 1

Sample Output
0
6

Author
WhereIsHeroFrom

Source

Recommend

 1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
5 {
6     int x=0,f=1;
7     char ch=getchar();
8     while(ch<'0'||ch>'9')
9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 inline void write(int x)
22 {
23     if(x<0)
24     {
25         putchar('-');
26         x=-x;
27     }
28     if(x>9)
29     {
30         write(x/10);
31     }
32     putchar(x%10+'0');
33 }
34 const int N=1001;
35 int n;
36 int num[N];
37 int c[N];
38 struct node
39 {
40     int x;
41     int id;
42 }q[N] ;
43 bool cmp(node a,node b)
44 {
45     return a.x<b.x;
46 }
47 int lowbit(int x)
48 {
49     return x&(-x);
50 }
51 int getsum(int x)
52 {
53     int s=0;
54     while(x>0)
55     {
56         s+=c[x];
57         x-=lowbit(x);
58     }
59     return s;
60 }
62 {
63     while(x<=n)
64     {
65         c[x]+=y;
66         x+=lowbit(x);
67     }
68 }
69 int main()
70 {
71     while(scanf("%d",&n)!=EOF)
72     {
73         memset(c,0,sizeof(c));
74         memset(num,0,sizeof(num));
75         for(int i=1;i<=n;i++)
76         {
77             scanf("%d",&q[i].x);
78             q[i].id=i;
79         }
80         sort(q+1,q+1+n,cmp);
81         for(int i=1;i<=n;i++)
82         {
83             num[q[i].id]=i;
84         }
85         int sum = 0;
86         for(int i=1;i<=n;i++)
87         {
89             sum+=getsum(n)-getsum(num[i]);
90         }
91         printf("%d\n",sum);
92     }
93     return 0;
94 }

+关注
angel_kitty