poj 2828 Buy Tickets (排隊(duì)問(wèn)題+線段樹)
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-04-29 08:08:04 閱讀次數(shù)：2547次
/*
//不想寫題解了,就直接把人家的粘過(guò)來(lái)了
線段樹節(jié)點(diǎn)中保存這1段中的空位數(shù)，然后倒序?qū)os插入：
例如：
0 77
1 51
1 33
2 69
先?。?2 69 ―― ―― ―69― ―― （需要前面有3個(gè)空位才能插入）
然后?。?1 33 ―― ―33― ―69― ―― （需要前面有2個(gè)空位才能插入）
然后?。?1 51 ―― ―33― ―69― ―51― （需要前面有2個(gè)空位才能插入） 前面只有1個(gè)空位 故插入后面空格
然后?。?0 77 ―77― ―33― ―69― ―51― （需要前面有1個(gè)空位才能插入）
#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就是此點(diǎn)要插入的位置
void bina_query(int p,int l,int r,int rt){
if(l==r&&p==sum[rt]){ //剛開(kāi)始少了(l==r)這個(gè)條件,由于必須是肯定到某點(diǎn)以后恰好為p,所以不加會(huì)錯(cuò)
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;
}
由于某個(gè)人想要插入posi位置，插入后他就在posi位置上了，但是可能其他人會(huì)插到他前面來(lái)，他的位置就會(huì)變成[在他后面且插在他位置及之前的人數(shù)]+posi
如果這樣就開(kāi)始求了，固然用線段樹就能夠做了，就跟求逆序數(shù)對(duì)1樣。
但是我們可以反著來(lái)斟酌，只要從后面開(kāi)始站，假定后面的人都已站在正確的位置上了，那末到那個(gè)人站的時(shí)候，現(xiàn)在的位置上已都是后面的那些人了，
只要數(shù)posi個(gè)空格，那那個(gè)人站的位置能肯定了。肯定以后就能夠求下1個(gè)了，所以這個(gè)條件和結(jié)論都成立了。
所以我們只要從后面人站起，數(shù)posi個(gè)空格站上去就好了。
線段樹的話跟求和線段樹1樣，初始化時(shí)全部初始化為1，然后查找的時(shí)候可以“2分”查找
*/
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
