首页 > 代码库 > poj万人题
poj万人题
poj提交数量过万的题，除了水爆了的题就是无比经典的，不得不刷的题。 准备将poj上提交次数过万的题刷个遍。 持续更新中。。。
poj 2828（线段树）
此题乃是Zhu, Zeyuan神牛出的，拿到题目就觉得这题真的是很有意思，苦想一天无果。 感叹大神的思维果真奇妙。 随随便便提出的问题都成为了如此经典。看了下讨论发现貌似不好想，再尝试了下发现有些问题还是没有想出解决掉方法，而且越来越混乱， 无奈只能看题解了。。。
由于插队是具有最高优先级，而且显然最后一个人插在哪里那么他的最终位置就是哪里。 所以可以从后往前看。先将最后一个人放好，再根据最后一个人的位置判断倒数第二个人的位置。 由此如果能在得知后n个点的位置推出从后往前第n+1个点的位置，那么这题就可以得到完美解决。直接模拟的话需要n*n的复杂度，明显不行。
用num[s]表示从l[s]到r[s]中还有多少空格可以放入(l[s]表示这段线段的左端点，r[s]表示这段线段的右端点)
当要插入到当前线段的第i个位置时，其实并不一定能插到i的位置，因为如果从起点到i上已经有点了，那么表示这点必须得后退，且出现一个点后退一步，且后退途中遇到新的点又得多后退一步。
到底是插入到左段还是右段 如果i<=num[2*s] （插入点的位置小于左段可插入的个数）,那么就插入左段，否则插入右段且更新插入位置，i变成i-(cntleft-cnthave) 或者i+cnthave-cntleft其中cntleft表示左端的点个数cnthave表示左端有多少点已经插入了。 这个是用线段树的关键所在，可以举几个例子推一下。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <string> 5 #include <algorithm> 6 #include <math.h> 7 #include <stdlib.h> 8 using namespace std; 9 #define N 20020010 11 int n;12 int gp[N],gv[N];13 int l[4*N],r[4*N],num[4*N];14 int ans[N];15 16 void build(int tl,int tr,int s)17 {18 l[s]=tl;19 r[s]=tr;20 if(tl==tr)21 {22 num[s]=1;23 return ;24 }25 int mid=(tl+tr)/2;26 build(tl,mid,2*s);27 build(mid+1,tr,2*s+1);28 num[s]=num[2*s]+num[2*s+1];29 }30 31 void update(int x,int w,int s)32 {33 if(l[s]==r[s])34 {35 ans[l[s]]=w;36 num[s]=0;37 return ;38 }39 if(x<=num[2*s])//左段又足够的空间，且要插入的位置比较靠前40 update(x,w,2*s);41 else //左段不够，必须得到右边42 update(x-num[2*s],w,2*s+1);43 num[s]--;44 }45 46 47 int main()48 {49 while(scanf("%d",&n)!=EOF)50 {51 memset(num,0,sizeof(num));52 build(1,n,1);53 for(int i=1;i<=n;i++)54 scanf("%d%d",gp+i,gv+i);55 for(int i=n;i>=1;i--)56 {57 update(gp[i]+1,gv[i],1);58 }59 for(int i=1;i<n;i++)60 printf("%d ",ans[i]);61 printf("%d\n",ans[n]);62 63 }64 return 0;65 }
poj万人题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。