自动搬运

查看原文

来自洛谷，原作者为

	ny_jerry2 **

搬运于2025-08-24 23:07:59，当前版本为作者最后更新于2025-01-07 12:10:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好题一道。

我们可以开一个栈，然后倒序枚举一下，遇到一个倒着走的粒子，就压入栈。否则，这个正着走的粒子就与栈顶组合。显然，这样是对的。

然后用双指针或二分技术就好了。

#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
int n,m;
const int N=5e5+10;
int x[N],type[N];
int t[N],tim[N];
stack<int> st;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&type[i]);
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		scanf("%d",&t[i]);
	}
	for(int i=n;i;i--){
		if(type[i]==-1){
			st.push(i);
		}else{
			if(st.empty()){
				continue;
			}
			int d=st.top();
			tim[i]=tim[d]=(x[d]-x[i]+1)/2;
			st.pop();
		}
	}
	for(int i=1;i<=n;i++){
		if(!tim[i]){
			tim[i]=2e9;
		}
	}
	sort(tim+1,tim+n+1);
	int j=0;
	for(int i=1;i<=m;i++){
		while(j<n&&tim[j+1]<=t[i]){
			j++;
		}
		printf("%d\n",n-j);
	}
}