专栏首页mlHDUOJ---3743Frosh Week(BIT+离散化)

HDUOJ---3743Frosh Week(BIT+离散化)

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...

    Gxjun
  • poj----1330Nearest Common Ancestors(简单LCA)

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

    Gxjun
  • hdu---(1280)前m大的数(计数排序)

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

    Gxjun
  • Java版SMS4加密解密算法

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

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

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

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

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

    attack
  • C++上机考试试题解析

    慕白
  • 图论--欧拉回路(模板)

    风骨散人Chiam
  • poj 1562 dfs

    瑾诺学长
  • UVA-11600-Masud Rana

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

    f_zyj

扫码关注云+社区

领取腾讯云代金券