# POJ 1804 Brainman(5种解法，好题，【暴力】，【归并排序】，【线段树单点更新】，【树状数组】，【平衡树】)

## Brainman

Time Limit: 1000MS

Memory Limit: 30000K

Total Submissions: 10575

Accepted: 5489

Description

Input

The first line contains the number of scenarios. For every scenario, you are given a line containing first the length N (1 <= N <= 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks.

Output

Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line.

Sample Input

```4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0```

Sample Output

```Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0```

Source

TUD Programming Contest 2003, Darmstadt, Germany

<1>.暴力大法，时间复杂度为O(n^2)

<2>.归并排序法,时间复杂度为O(n*log n)

<3>.线段树单点更新，时间复杂度为O(log n)

``` 1 #include <iostream>
2 #include <stdio.h>
3 using namespace std;
4 const int N=200020;
5 int a[N],b[N];
6 int main()
7 {
8     int n;
9     scanf("%d",&n);
10     for(int k=1;k<=n;k++)
11     {
12         int m;
13         scanf("%d",&m);
14         for(int i=1;i<=m;i++)
15             scanf("%d",&a[i]);
16             int ans=0;
17             for(int i=1;i<=m;i++)
18                 for(int j=i+1;j<=m;j++)
19                 if(a[i]>a[j])
20                 ans++;
21             printf("Scenario #%d:\n%d\n\n",k,ans);
22     }
23     return 0;
24 }```

``` 1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 using namespace std;
5 const int max_n = 1000 + 10;
6
7 int n, a[max_n];
8 int tmp[max_n], ans;
9
10 void merge(int *a, int *tmp, int l, int mid, int r)
11 {
12     if (l >= r)  return;
13     int i = l, j = mid + 1, k = 0;
14     int count = 0, flag = 0;
15     while (i <= mid && j <= r)
16     {
17         if (a[i] <= a[j])
18         {
19             tmp[k ++] = a[i++];
20             ans += j - mid - 1;
21         }else   tmp[k ++ ] =  a[j++];
22     }
23     while (i <= mid) tmp[k ++] = a[i++], ans += r- mid;
24     while (j <= r)       tmp[k ++] = a[j++];
25     for (i = 0; i != k; ++ i)   a[l + i] = tmp[i];
26 }
27
28 void mergesort(int *a, int *tmp, int l, int r)
29 {
30     if (l >= r)  return;
31     int mid = (l + r) / 2;
32     mergesort(a, tmp, l, mid);
33     mergesort(a, tmp , mid + 1, r);
34     merge(a, tmp, l, mid, r);
35 }
36
37 int main()
38 {
39     int tt;
40     scanf("%d", &tt);
41     for (int i = 1; i <= tt; ++ i)
42     {
43         cout<<"Scenario #"<<i<<":"<<endl;
44         scanf("%d", &n);
45         ans = 0;
46         for (int i = 0; i != n; ++ i)   scanf("%d", &a[i]);
47         mergesort(a, tmp, 0, n - 1);
48         cout<<ans<<endl<<endl;
49     }
50 }```

n个数扫一边 遇到一个值i加到线段树上  查（i+1，n），再求和输出！

```  1 #include <map>
2 #include <iostream>
3 #include <set>
4 #include <cstdio>
5 #include <cstdlib>
6 using namespace std;
7
8 const int max_n = 1000 + 10;
9
10 int n;
11 int a[max_n], count;
12 map<int, int>G;
13 map<int, int>::iterator it;
14
15
16
17 struct node
18 {
19     int cd, key;
20     int ls, rs;
21     int L, R;
22     node():L(0),R(0),ls(0),rs(0),cd(0),key(0){};
23     void clear()
24     {
25         cd = key = 0;
26     }
27 }t[max_n * 3];
28 int tail = 1;
29
30
31 void init()
32 {
33     for (int i = 0; i != max_n * 3; ++ i)    t[i].clear();
34     G.clear();
35     scanf("%d", &n);
36     for (int i = 0; i != n; ++ i)
37     {
38         scanf("%d", &a[i]);
39         G[a[i]] = 0;
40     }
41     count = 0;
42     for (it = G.begin(); it != G.end(); ++ it)    it -> second = ++ count;
43 }
44
45
46
47 void make_tree(int now, int LL, int RR)
48 {
49     t[now].L = LL;
50     t[now].R = RR;
51     if (LL == RR)    return;
52     int mid = (LL + RR)/ 2;
53     make_tree(t[now].ls = ++ tail, LL, mid);
54     make_tree(t[now].rs = ++ tail, mid + 1, RR);
55 }
56
57 void tran(int now)
58 {
59     int left_son = t[now].ls, right_son = t[now].rs;
60     t[left_son].cd += t[now].cd;
61     t[right_son].cd += t[now].cd;
62     t[now].key += t[now].cd;
63     t[now].cd = 0;
64 }
65
66 void ins(int now, int LL, int RR)
67 {
68
69     tran(now);
70     if (t[now].L == LL && t[now].R == RR)
71     {
72         t[now].cd ++;
73         return;
74     }
75     t[now].key ++;
76     int mid = (t[now].L + t[now].R) / 2;
77     if (RR <= mid)    {ins(t[now].ls, LL, RR); return;}
78     if (mid < LL)    {ins(t[now].rs, LL, RR); return;}
79     ins(t[now].ls, LL, mid);
80     ins(t[now].rs, mid + 1, RR);
81 }
82
83 int find(int now, int LL, int RR)//因为题目的特殊性，只会找一个……
84 {
85     tran(now);
86     if (t[now].L == LL  && t[now].R == RR)    return t[now].key;
87     int mid = (t[now].L + t[now].R) / 2;
88     if (RR <= mid)    return find(t[now].ls, LL, RR);
89     if (mid < LL)    return find(t[now].rs, LL, RR);
90     cout<<"wtf?"<<endl;
91 }
92
93 void doit()
94 {
95     int ans=0;
96     for (int i = 0; i != n; ++ i)
97     {
98         int num = G[a[i]];
99         ans += find(1, num + 1, num + 1);
100         ins(1, 0, num);
101     }
102     cout<<ans<<endl;
103 }
104
105 int main()
106 {
107     int tt;
108     scanf("%d",&tt);
109     make_tree(1, 0, 1002);
110     for (int i = 1; i <= tt; ++ i)
111     {
112         cout<<"Scenario #"<<i<<":"<<endl;
113         init();
114         doit();
115         cout<<endl;
116     }
117 }```

``` 1 #include <cstdio>
2 #include <cstdlib>
3 #include <map>
4 #include <cstring>
5 using namespace std;
6 #define lowbit(k) ((k)&(-k))
7
8 const int max_n = 1000 + 10;
9 int n, a[max_n], s[max_n];
10 map<int, int>G;
11 map<int, int>::iterator it;
12 int count;
13 void init()
14 {
15     scanf("%d", &n);
16     G.clear();
17     count = 1;
18     memset(s, 0, sizeof(s));
19     for (int i = 0; i != n; ++ i)
20     {
21         scanf("%d", &a[i]);
22         G[a[i]] = 0;
23     }
24     for (it = G.begin(); it != G.end(); ++ it)    it -> second = ++ count;
25 }
26
27 void ins(int k)
28 {
29     s[k] += 1;
30     while ((k += lowbit(k)) <= 1000)    s[k] += 1;
31 }
32
33
35 {
36     int tot = s[k];
37     while (k -= lowbit(k))    tot += s[k];
39 }
40
41
42 void doit()
43 {
44     int ans = 0;
45     for (int i = 0; i != n; ++ i)
46     {
47         int num = G[a[i]];
49         ins(num);
50     }
51     printf("%d\n",ans);
52 }
53
54 int main()
55 {
56     int tt;
57     scanf("%d", &tt);
58     for (int i = 1; i <= tt; ++ i)
59     {
60         printf("Scenario #%d:\n",i);
61         init();
62         doit();
63         printf("\n");
64     }
65 }```

```  1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 using namespace std;
5 const int max_n = 1000 + 10;
6
7 int n;
8 const int maxint = 0x7fffffff;
9
10 struct node
11 {
12     node *c[2];
13     int key;
14     int size;
15     node():key(0),size(0)
16     {
17         c[0] = c[1] = this;
18     }
19     node(int KEY_, node *a0, node *a1):
20     key(KEY_){c[0] =a0, c[1]=a1;}
21     node* rz(){return size = c[0]->size + c[1]->size + 1, this;}
22 }Tnull, *null=&Tnull;
23
24 struct splay
25 {
26     node *root;
27     splay()
28     {
29         root = (new node(*null)) -> rz();
30         root -> key = maxint;
31     }
32     void zig(int d)
33     {
34         node *t = root -> c[d];
35         root -> c[d]  = null -> c[d];
36         null -> c[d] = root;
37         root = t;
38     }
39     void zigzig(int d)
40     {
41         node *t = root -> c[d] -> c[d];
42         root -> c[d] -> c[d] = null -> c[d];
43         null -> c[d] = root -> c[d];
44         root -> c[d] = null -> c[d] -> c[!d];
45         null -> c[d] -> c[!d] = root -> rz();
46         root = t;
47     }
48
49     void finish(int d)
50     {
51         node *t = null -> c[d], *p = root -> c[!d];
52         while (t != null)
53         {
54             t = null -> c[d] -> c[d];
55             null -> c[d]  -> c[d] = p;
56             p = null -> c[d] -> rz();
57             null -> c[d] = t;
58         }
59         root -> c[!d] = p;
60     }
61     void select(int k)//谁有k个儿子
62     {
63         int t;
64         while (1)
65         {
66             bool d = k > (t = root -> c[0] -> size);
67             if (k == t || root -> c[d] == null)    break;
68             if (d)    k -= t + 1;
69             bool dd = k > (t = root -> c[d] -> c[0] -> size);
70             if (k == t || root -> c[d] -> c[dd] == null){zig(d); break;}
71             if (dd) k -= t + 1;
72             d != dd ? zig(d), zig(dd) : zigzig(d);
73         }
74         finish(0), finish(1);
75         root -> rz();
76     }
77     void search(int x)
78     {
79         while (1)
80         {
81             bool d = x > root -> key;
82             if (root -> c[d] == null)    break;
83             bool dd = x > root -> c[d] -> key;
84             if (root -> c[d] -> c[dd] == null){zig(d); break;}
85             d != dd ? zig(d), zig(dd) : zigzig(dd);
86         }
87         finish(0), finish(1);
88         root -> rz();
89         if (x > root -> key)    select(root -> c[0] -> size + 1);
90     }
91
92     void ins(int x)
93     {
94         search(x);
95         node *oldroot = root;
96         root = new node(x, oldroot -> c[0],oldroot);
97         oldroot -> c[0] = null;
98         oldroot -> rz();
99         root -> rz();
100     }
101     int sel(int k){return select(k - 1), root -> key;}
102     int ran(int x){return search(x), root -> c[0] -> size + 1;}
103 }*sp;
104
105
106 int main()
107 {
108     int tt;
109     scanf("%d", &tt);
110     for (int i = 1; i <= tt; ++ i)
111     {
112         sp = new splay;
113         cout<<"Scenario #"<<i<<":"<<endl;
114         scanf("%d", &n);
115         int ans = 0;
116         int tmp;
117         for (int i = 0; i != n; ++ i)
118         {
119             scanf("%d", &tmp);
120             tmp = - tmp;
121             ans +=     sp -> ran(tmp) - 1;
122             //cout<<sp.ran(tmp) - 1<<endl;
123             sp -> ins(tmp);
124         }
125         delete sp;
126         cout<<ans<<endl<<endl;
127     }
128 }```

780 篇文章62 人订阅

0 条评论

## 相关文章

### 3339: Rmq Problem

Description image.png Input image.png Output image.png Sample Input 7 5 ...

33911

### 1901: Zju2112 Dynamic Rankings

1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

2766

### LWC 58：724. Find Pivot Index

LWC 58：724. Find Pivot Index 传送门：724. Find Pivot Index Problem: Given an array ...

1978

8438

4596

2149

2331

### 2243: [SDOI2011]染色

2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

2949

### 《Kotin 编程思想·实战》

Xtend是Eclipse推出的一个新的JVM语言，并无意替代Java，而是以己之长补Java之短，精简代码，无类型，改进可读和维护。Eclipse Xtend...

1203

2383