HDU 2689 Sort it(ツリー配列)
8902 ワード
タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=2689
Sort it
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
(私のコードでは この問題はb[i]配列と密接に関連している.
b[i]表示
配列aをあげるとしたら[ ] = {2,5,3,4,1},b[i],b[i]を求める a[1],a[2]…a[i-1]において(即位置iの左側)a[i]に等しい数より小さい個数を表す.
大神たちは私がやったのではないようで、私は奇抜なルートを歩いたことがあります. ふふ..
View Code
Sort it
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
(私のコードでは この問題はb[i]配列と密接に関連している.
b[i]表示
配列aをあげるとしたら[ ] = {2,5,3,4,1},b[i],b[i]を求める a[1],a[2]…a[i-1]において(即位置iの左側)a[i]に等しい数より小さい個数を表す.
大神たちは私がやったのではないようで、私は奇抜なルートを歩いたことがあります. ふふ..
1 #include<iostream>
2
3 using namespace std ;
4
5 int sum[1005];
6 int n ;
7
8 int lowbit(int x) // x 1， 4， 4， 5， 1
9 {
10 return x&(-x);
11 }
12
13 void update(int i, int val) // i val
14 {
15 //i val
16 while(i <= n)
17 {
18 sum[i] += val;
19 i += lowbit(i); // i
20 }
21 }
22
23 int Sum(int i) // i
24 {
25 int s = 0;
26 // i
27 while(i > 0)
28 {
29 s += sum[i];
30 i -= lowbit(i); // i
31 }
32 return s;
33 }
34
35 int main()
36 {
37 int i;
38 int a[1005],b[1005];
39 while(scanf("%d",&n)!=EOF)
40 {
41 int count=0;
42 memset(b,0,sizeof(b));
43 memset(sum,0,sizeof(sum));
44 for(i=1;i<=n;i++)
45 {
46 scanf("%d",&a[i]);
47 }
48
49 for(i=1;i<=n; i++)
50 {
51 b[i] = Sum(a[i]); // a[i]
52 update(a[i],1); // a[i] +1
53 count+=i-b[i]-1;
54 }
55
56
57 cout<<count<<endl;
58
59 }
60
61 return 0;
62 }View Code