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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

3339: Rmq Problem

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

33911
来自专栏HansBug's Lab

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
来自专栏jeremy的技术点滴

写py2、py3兼容的代码

8438
来自专栏JavaEdge

SpringMVC数据绑定定义支持的数据绑定方式

定义 百度百科定义: 简单绑定是将一个用户界面元素(控件)的属性绑定到一个类型(对象)实例上的某个属性的方法。 例如,如果一个开发者有一个Customer类...

4596
来自专栏拭心的安卓进阶之路

Java 集合源码解析(2):ListIterator

今天心情和股票一样红,还是学学 ListIterator 吧! ListIterator ? 根据官方文档介绍, ListIterator 有以下功能: 允许...

2149
来自专栏java一日一条

UML类图五种关系与代码的对应关系

注意1: Water类的生命期,它是当Animal类的GrounUp方法被调用的时候,才被实例化。

2331
来自专栏HansBug's Lab

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
来自专栏晓晨的专栏

C#自动识别文件编码

2383

扫码关注云+社区

领取腾讯云代金券