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

Brainman

Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 10575   Accepted: 5489

Description

Background
Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task.

Problem
Here‘s what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example:Start with: 2 8 0 3
swap  (2 8) 8 2 0 3
swap  (2 0) 8 0 2 3
swap  (2 3) 8 0 3 2
swap  (8 0) 0 8 3 2
swap  (8 3) 0 3 8 2
swap  (8 2) 0 3 2 8
swap  (3 2) 0 2 3 8
swap  (3 8) 0 2 8 3
swap  (8 3) 0 2 3 8So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps:Start with: 2 8 0 3
swap  (8 0) 2 0 8 3
swap  (2 0) 0 2 8 3
swap  (8 3) 0 2 3 8The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond‘s mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it.

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

题目链接:http://poj.org/problem?id=1804

分析:求逆序数的大水题,虽然这题数据给的范围很小,暴力都可以过,写不来的时候直接暴力就可以过,如果数据改大了就必然TL,想想看还有啥方法!

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

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

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

第一种暴力大法,请看AC代码:

 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 }

第二种归并排序, 对2个已经排好序的数列,进行再排序,只需要把2个数列,从头到尾,按顺序,谁小,谁就先进入tmp数组, 最后tmp数组一定排好序了,然后把TMP数组的元素复制回原数组中即可。

同理,如果我们知道2个子序列的逆序对数量,是否可以通过归并排序一样,求出整体的数量呢?显然是可以的。

这里有一个地方,当左边的数列的a[k]要进tmp数组了, 这个时候,如果右边的指针指向a+mid+p,就说明a[k]比a[mid+1]...a[mid + 2]..a[mid+3].....a[mid+p]都要大!【重要】

也就是说,对于a[k]而言,整个数列中, mid+ mid+2...mid+p都在k后面,同时a[k]比a[mid+1],a[mid+2]...a[mid+p]都要大。 那么显然是增加逆序对数量的。 通过整个方法,计算出整个逆序对的数量即可。

下面给出AC代码:

 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),再求和输出!

下面给出AC代码:

  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
34 int ask(int k)//1..k的和
35 {
36     int tot = s[k];
37     while (k -= lowbit(k))    tot += s[k];
38     return tot;
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]];
48         ans += ask(count) - ask(num);
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 }

第五种:平衡树

只要查找,当前在树中,有多少个数字比a[k]要大, 因为是按顺序插入的,所以这个数字的数量就是逆序对的个数

这里有一个小技巧,如果平衡树每次要删的话很麻烦,直接用写成struct,然后新的树就new,最后delete掉即可~

  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 }
时间: 05-02

POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)的相关文章

HDU 1166 敌兵布阵(线段树单点更新,板子题)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 87684    Accepted Submission(s): 36912 Problem Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务

线段树 --- (单点更新、求区间最值、模板题)

A - 敌兵布阵 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了.A国在海岸线沿直线布置了N个工兵营 地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况.由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工 兵营地的人数都有可能发生

POJ训练计划2828_Buy Tickets(线段树/单点更新)

解题报告 题意: 插队完的顺序. 思路: 倒着处理数据,第i个人占据第j=pos[i]+1个的空位. 线段树维护区间空位信息. #include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int x,v; } num[201000]; int sum[1000000],ans[201000]; void cbtree(int rt,int l,in

POJ 3264 Balanced Lineup (线段树单点更新 区间查询)

Balanced Lineup Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 36820   Accepted: 17244 Case Time Limit: 2000MS Description For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer Joh

POJ训练计划2299_Ultra-QuickSort(线段树/单点更新)

解题报告 题意: 求逆序数. 思路: 线段树离散化处理. #include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #define LL long long using namespace std; LL sum[2001000],num[501000],_hash[501000]; void push_up(int rt) { sum[rt]=sum[rt*2

POJ 2828 Buy Tickets (线段树 单点更新 变形)

题目链接 题意:有N个人排队,给出各个人想插队的位置和标识,要求输出最后的序列. 分析:因为之前的序列会因为插队而变化,如果直接算时间复杂度很高,所以可以用 线段树逆序插入,把序列都插到最后一层,len记录该区间里还剩余多少位置,插入的时候就插到剩余的第几个位置, 比如1,2已经插入了,如果再想插入第3个位置,则实际上插入的是5. 因为是逆序的,所以在3之前除了现在的1,2 还有之前的1,2. 1 #include <iostream> 2 #include <cstdio> 3

Buy Tickets+POJ+线段树单点更新的灵活运用

Buy Tickets Time Limit: 4000MS   Memory Limit: 65536K Total Submissions: 12927   Accepted: 6410 Description Railway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join a long queue- The Lunar New Year wa

poj 2886 Who Gets the Most Candies? (线段树单点更新应用)

poj 2886 Who Gets the Most Candies? Description N children are sitting in a circle to play a game. The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from t

CDOJ 1073 线段树 单点更新+区间查询 水题

H - 秋实大哥与线段树 Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%lld & %llu Submit Status Practice UESTC 1073 Appoint description:  System Crawler  (2016-04-24) Description “学习本无底,前进莫徬徨.” 秋实大哥对一旁玩手机的学弟说道. 秋实大哥是一个爱学习的人,今天他刚刚学习了线段树这个数据结构. 为