Frosh Week

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

Problem Description

During Frosh Week, students play various fun games to get to know each other and compete against other teams. In one such game, all the frosh on a team stand in a line, and are then asked to arrange themselves according to some criterion, such as their height, their birth date, or their student number. This rearrangement of the line must be accomplished only by successively swapping pairs of consecutive students. The team that finishes fastest wins. Thus, in order to win, you would like to minimize the number of swaps required.

Input

The first line of input contains one positive integer n, the number of students on the team, which will be no more than one million. The following n lines each contain one integer, the student number of each student on the team. No student number will appear more than once.

Output

Output a line containing the minimum number of swaps required to arrange the students in increasing order by student number.

Sample Input

3 3 1 2

Sample Output

2

Source

University of Waterloo Local Contest 2010.10.02

``` 1 /*
2  树状数组求逆序数
3 */
4 #include<stdio.h>
5 #include<string.h>
6 #include<stdlib.h>
7 #define maxn 1000000
8 int nn;
9 __int64 tol;
10 int aa[maxn+5];
11
12 struct node
13 {
14     int id;
15     int val;
16 }stu[maxn+5];
17 //低位操作
18 int lowbit(int x)
19 {
20     return x&(-x);
21 }
22
23 void ope(int x)
24 {
25     while(x<=nn)
26     {
27         aa[x]++;
28         x+=lowbit(x);
29     }
30 }
31
32 __int64 sum(int x)
33 {
34      __int64 ans=0;
35     while(x>0)
36     {
37      ans+=aa[x];
38      x-=lowbit(x);
39     }
40     return ans;
41 }
42 int cmp(void const *a,void const *b)
43 {
44     return (*(struct node *)a).val - (*(struct node *)b).val;
45 }
46 int main()
47 {
48     int i,val;
49     while( scanf("%d",&nn)!=EOF)
50     {
51         tol=0;
52         memset(aa,0,sizeof(int)*(nn+5));
53         for(i=0;i<nn;i++)
54         {
55             scanf("%d",&stu[i].val);
56             stu[i].id=i+1;
57         }
58         qsort(stu,nn,sizeof(struct node),cmp);
59         for(i=0;i<nn;i++)
60         {
61             tol+=sum(nn)-sum(stu[i].id);
62             ope(stu[i].id);
63         }
64         printf("%I64d\n",tol);
65     }
66     return 0;
67 }```

``` 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define maxn 1000000
5 int aa[maxn+5];
6 int cc[maxn+5];
7 __int64 tol;
8 void merge(int low ,int mid ,int hight)
9 {
10     int i,j,k;
11     i=low;
12     j=mid;
13     k=0;
14     while(i<mid&&j<hight)
15     {
16         if(aa[i]>aa[j])
17         {
18             cc[k++]=aa[j++];
19             tol+=mid-i;
20         }
21         else
22           cc[k++]=aa[i++];
23     }
24     for( ; i<mid; i++)
25         cc[k++]=aa[i];
26     for( ; j<hight ; j++ )
27         cc[k++]=aa[j];
28     k=0;
29     for(i=low;i<hight;i++)
30       aa[i]=cc[k++];
31 }
32 void merge_sort(int st ,int en)
33 {
34     int mid;
35     if(st+1<en)
36     {
37         mid=st+(en-st)/2;
38         merge_sort(st,mid);
39         merge_sort(mid,en);
40         merge(st,mid,en);
41     }
42 }
43
44 int main()
45 {
46     int n,i;
47     while(scanf("%d",&n)!=EOF)
48     {
49         tol=0;
50         for(i=0;i<n;i++)
51             scanf("%d",aa+i);
52         merge_sort(0,n);
53         printf("%I64d\n",tol);
54     }
55  return 0;
56 }```

非递归版的归并排序

``` 1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define maxn 1000000
5 int aa[maxn+5];
6 int cc[maxn+5];
7 __int64 tol;
8 void merge(int low ,int mid ,int hight)
9 {
10     int i,j,k;
11     i=low;
12     j=mid;
13     k=0;
14     while(i<mid&&j<hight)
15     {
16         if(aa[i]>aa[j])
17         {
18             cc[k++]=aa[j++];
19             tol+=mid-i;
20         }
21         else
22           cc[k++]=aa[i++];
23     }
24     for( ; i<mid; i++)
25         cc[k++]=aa[i];
26     for( ; j<hight ; j++ )
27         cc[k++]=aa[j];
28     k=0;
29     for(i=low;i<hight;i++)
30       aa[i]=cc[k++];
31 }
32 void merge_sort(int st,int en)
33 {
34     int s,t,i;
35     t=1;
36     while(t<=(en-st))
37     {
38         s=t;
39         t=2*t;
40         i=st;
41         while(t+i<=en)
42         {
43             merge(i,i+s,i+t);
44             i+=t;
45         }
46         if(i+s<en)
47             merge(i,i+s,en);
48     }
49     if(st+s<en)
50         merge(st,st+s,en);
51
52 }
53
54 int main()
55 {
56     int n,i;
57     while(scanf("%d",&n)!=EOF)
58     {
59         tol=0;
60         for(i=0;i<n;i++)
61             scanf("%d",aa+i);
62         merge_sort(0,n);
63         printf("%I64d\n",tol);
64     }
65  return 0;
66 }```

0 条评论

• poj-----Ultra-QuickSort(离散化+树状数组)

Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536K Total Submission...

• poj----1330Nearest Common Ancestors（简单LCA)

题目连接  http://poj.org/problem?id=1330 就是构建一棵树，然后问你两个节点之间最近的公共父节点是谁？ 代码： 1 /*Sour...

• hdu---（1280）前m大的数（计数排序）

前m大的数 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

• Java版SMS4加密解密算法

最近工作中需要实现HBase自定义扩展sms4加密，今天就先来说一下Java版的SMS4加密解密算法的具体实现。

• 洛谷P4065 [JXOI2017]颜色(线段树)

所以我们可以对于每个右端点，统计最长的左端点在哪里，刚开始以为这个东西有单调性，但事实并不是这样。。

• 洛谷P3722 [AH2017/HNOI2017]影魔(线段树)

对于本题而言，我们可以预处理出每个位置左边第一个比他大的位置\(l_i\)以及右边第一个比他大的位置\(r_i\)

• UVA-11600-Masud Rana

ACM模版 描述 ? ? 题解 image.png ? 保存六位小数…… 代码 #include <cstdio> #include <cstring> #in...