poj 2828 Buy Tickets (排队问题+线段树)

/*
    //不想写题解了,就直接把人家的粘过来了
    线段树节点中保存这1段中的空位数,然后倒序对pos插入:
    例如:  
         0 77
         1 51
         1 33
         2 69
  先取: 2 69  ――  ――  ―69―   ――   (需要前面有3个空位才能插入)
       然后取: 1 33   ――   ―33―    ―69―    ――   (需要前面有2个空位才能插入)
       然后取: 1 51   ――   ―33―    ―69―    ―51―   (需要前面有2个空位才能插入)  前面只有1个空位  故插入后面空格
  然后取: 0 77   ―77―   ―33―    ―69―    ―51―   (需要前面有1个空位才能插入)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 200005
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<2],a,b;
struct qw{
int a,val,num;
}an[maxn];
int cmp(struct qw x,struct qw y){
return x.num<y.num;
}
void push_up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
sum[rt]=1; return;
}
int m=(l+r)>>1;
build(lson); build(rson);
push_up(rt);
}
void update(int p,int l,int r,int rt){
if(l==r){
sum[rt]=0; return;
}
int m=(l+r)>>1;
if(p<=m) update(p,lson);
else update(p,rson);
push_up(rt);
}
int q;
//2分查找q,使得sum(1,q)==p; i就是此点要插入的位置
void bina_query(int p,int l,int r,int rt){
if(l==r&&p==sum[rt]){ //刚开始少了(l==r)这个条件,由于必须是肯定到某点以后恰好为p,所以不加会错
q=r; return;
}
int m=(l+r)>>1;
if(p<=sum[rt<<1]) bina_query(p,lson);
else bina_query(p-sum[rt<<1],rson);
}
int main(){
int i,j,n;
while(~scanf("%d",&n)){
build(1,n,1);
for(i=1;i<=n;i++) scanf("%d%d",&an[i].a,&an[i].val);
//倒着插入
for(i=n;i>=1;i–){
bina_query(an[i].a+1,1,n,1);
an[i].num=q;
update(q,1,n,1);
}
sort(an+1,an+1+n,cmp);
for(i=1;i<n;i++) printf("%d ",an[i].val);
printf("%d
",an[i].val);
}
return 0;
}

   由于某个人想要插入posi位置,插入后他就在posi位置上了,但是可能其他人会插到他前面来,他的位置就会变成[在他后面且插在他位置及之前的人数]+posi
   如果这样就开始求了,固然用线段树就能够做了,就跟求逆序数对1样。
   但是我们可以反着来斟酌,只要从后面开始站,假定后面的人都已站在正确的位置上了,那末到那个人站的时候,现在的位置上已都是后面的那些人了,
   只要数posi个空格,那那个人站的位置能肯定了。肯定以后就能够求下1个了,所以这个条件和结论都成立了。
   所以我们只要从后面人站起,数posi个空格站上去就好了。
   线段树的话跟求和线段树1样,初始化时全部初始化为1,然后查找的时候可以“2分”查找
*/

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » poj 2828 Buy Tickets (排队问题+线段树)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡