题解：P10688 Buy Tickets

这是一道好题。

\color{blue}{\texttt{[Problem Discription]}}

n

个人依次来队伍里排队，其中第

i

个人来后会排在当前队伍中第

\text{pos}_{i}

个人的后面。若

\text{pos}_{i}=0

，则代表插队到队首。求最终队伍的顺序。

1\leq n \leq 2 \times 10^{5}

。

\color{blue}{\texttt{[Analysis]}}

考虑

p_{i}

表示第

i

个来的人最终排在哪一个位置。

第

i

个人会排在第

\text{pos}_{i}

个人的后面，于是后面的人的

p

都会加一。但是下标并不连续，因此无法用线段树或树状数组维护。

正面思考遇到困难。

很巧妙的正难则反。我们先考虑第

n

个来插队的人最终排在了哪里。

显然他就排在

(\text{pos}_{n}+1)

这个位置。

为什么是这个位置？因为这个位置前面有

\text{pos}_{n}

个空位。

于是第

i

个人插队时，问题转化为哪一个位置前面恰好有

\text{pos}_{i}

个空位。

可以二分配套树状数组求解。

\color{blue}{\text{Code}}

CPP

const int N=2e5+100;

class Fenwick_Tree{
	public:
		void modify(int pos,int val){
			for(int i=pos;i<=n;i+=lowbit(i))
				c[i]+=val;
		}
		int query(int pos){
			int res=0;
			for(int i=pos;i;i-=lowbit(i))
				res+=c[i];
			return res;
		}
		
		void init(int n=0){
			this->n=n;
			for(int i=1;i<=n;i++)
				c[i]=0;
		}
	private:
		int c[N],n;
		
		int lowbit(int x){
			return x&(-x);
		}
};

Fenwick_Tree ft;

int pos[N],rec[N],val[N],n;

int Bineary_Search(int pos){
	int l=1,r=n,res=1;
	while (l<=r){
		int mid=(l+r)>>1;
		
		if (ft.query(mid-1)<=pos){
			res=mid;
			l=mid+1;
		}
		else r=mid-1;
	}
	
	return res;
}

int main(){
	while (~scanf("%d",&n)){
		ft.init(n);
		
		for(int i=1;i<=n;i++){
			pos[i]=read();
			val[i]=read();
		}
		
		for(int i=1;i<=n;i++)
			ft.modify(i,1);
		
		for(int i=n;i>=1;i--){
			int p=Bineary_Search(pos[i]);
			
			ft.modify(p,-1);
			rec[p]=i;
		}
		
		for(int i=1;i<=n;i++)
			printf("%d%c",val[rec[i]],(i==n?'\n':' '));
	}
	
	return 0;
}

题解：P10688 Buy Tickets

文章操作

相关推荐

评论

题解：P10688 Buy Tickets