首页 > 代码库 > HDU 3743 Frosh Week （线段树+离散化）
HDU 3743 Frosh Week （线段树+离散化）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3743
Frosh Week
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 5 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
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
题解：
/*本题给定一个数n,然后给出n个数的序列，
要求最少交换多少次可使原序列变成递增的。
根据以往的经验，也就是求序列的逆序数的和。
可用线段树破之。
但本题有个陷阱，即原序列中的n个数并没说是从1到n的某个排列。
对此我们可以先进行离散化。离散化在本题很简单，
只需记录数在原序列中的下标，然后按数值从小到大排序。
排序后的下表id对应该数在原数组中的相对大小，
然后我们按从小到大的顺序插入，查询。*/
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int MAXN=1000000+100; 8 struct node 9 {10 int num,id;11 }Per[MAXN];12 13 int C[MAXN];14 int Lowbit[MAXN];15 16 //C[i] = a[i-lowbit(i)+1] + …+ a[i],下表从1开始17 //Lowbit[i]=i&(i^(i-1));或Lowbit[i]=i&(-i); 18 //1.查询19 20 int QuerySum(int p)21 //查询原数组中下标1-p的元素的和 22 { 23 int nSum=0; 24 while(p>0) 25 { 26 nSum+=C[p]; 27 p-=Lowbit[p]; 28 } 29 return nSum; 30 } 31 32 //2.修改+初始化33 void Modify(int p,int val) 34 //原数组中下表为p的元素+val，导致C[]数组中部分元素值的改变35 { 36 while(p<=MAXN-10) 37 { 38 C[p]+=val; 39 p+=Lowbit[p]; 40 } 41 } 42 //**********************************************43 44 bool cmp(node a,node b)45 {46 return a.num<b.num;47 }48 49 50 int main()51 {52 int n,i;53 __int64 ans;54 for(i=1;i<MAXN;i++)55 Lowbit[i]=i&(-i);56 while(~scanf("%d",&n))57 {58 for(i=1;i<=n;i++)59 //scanf("%d",&da[i]);60 {61 scanf("%d",&Per[i].num);62 Per[i].id=i;63 }64 memset(C,0,sizeof(C));65 ans=0;66 sort(Per+1,Per+n+1,cmp);67 for(i=1;i<=n;i++)68 {69 ans+=(__int64)QuerySum(n)-(__int64)QuerySum(Per[i].id);70 Modify(Per[i].id,1);71 }72 printf("%I64d\n",ans);73 }74 return 0;75 }
ps：本来是在树状数组专题做的题目，结果自己写了好几次 RE MLT WA 各种错误都出现过 还是没有A掉 无语了
下面是我的错误代码 请无视 谢谢 囧
1 /*自己的错误代码 0.0*/ 2 /*re mlt wa 好无语*/ 3 #include<iostream> 4 5 using namespace std ; 6 7 const int MAXN=1000000+100; 8 9 int sum[MAXN];10 int n ;11 12 int lowbit(int x) //取x的最低位1，比如4，则返回4，如5，则返回113 {14 return x&(-x);15 }16 17 void update(int i, int val) //将第i个元素增加val18 {19 //i的祖先都要增加val20 while(i <= n)21 {22 sum[i] += val;23 i += lowbit(i); //将i的二进制未位补为得到其祖先24 }25 }26 27 int Sum(int i) //求前i项的和28 {29 int s = 0;30 //将前i项分段31 while(i > 0)32 {33 s += sum[i];34 i -= lowbit(i); //去掉i的二进制最后一个35 }36 return s;37 }38 39 int main()40 {41 int i;42 int a[1005],b[1005];43 while(scanf("%d",&n)!=EOF)44 {45 int count=0;46 memset(b,0,sizeof(b));47 memset(sum,0,sizeof(sum));48 for(i=1;i<=n;i++)49 {50 scanf("%d",&a[i]);51 }52 53 for(i=1;i<=n; i++)54 {55 b[i] = Sum(a[i]); //求前a[i]项的和56 update(a[i],1); //第a[i]个元素+157 count+=i-b[i]-1;58 }59 60 61 cout<<count<<endl;62 63 64 }65 66 return 0;67 }