poj 2828 Buy Tickets (排队问题+线段树)
发布时间：2020-12-13 20:07:56 所属栏目：PHP教程 来源：网络整理
导读：/* //不想写题解了,就直接把人家的粘过来了 线段树节点中保存这1段中的空位数，然后倒序对pos插入： 例如： 0 77 1 51 1 33 2 69 先取： 2 69 ―― ―― ―69― ―― （需要前面有3个空位才能插入） 然后取： 1 33 ―― ―33― ―69― ―― （需要前面有2个空
|
/* //不想写题解了,就直接把人家的粘过来了 线段树节点中保存这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 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 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,1);
an[i].num=q;
update(q,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分”查找 */ （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |