自动搬运

查看原文

来自洛谷，原作者为

	droplet ** 看着两百多行的代码行行都有错，这使你充满了决心　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　*

搬运于2025-08-24 22:55:39，当前版本为作者最后更新于2025-08-19 15:29:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目分析

对于某一时刻，第一个碰撞的两点只能是两个相邻的点。

此时我们可以通过双端链表存储没有湮灭的点。

通过题目描述，点的运动轨迹可以理解为先向一边 $s_i$ 单位，回到原来的点后再向另一边 $s_i$ 单位，向这一边 $2 \times s_i$ 单位，回到原来的点后再向另一边 $2 \times s_i$ 单位，以此类推，我们可以 $O(1)$ 的时间复杂度下求出任意两点的湮灭时间。

第一版思路

每次暴力求出任意两相邻点的湮灭时间，用双端链表删点。

优化

若直接暴力枚举的话只能过测试点 $1-7$，考虑用更快地方法算出湮灭时间。

注意到上方思路可转化为，每次要求一个集合的最小值，加入一个值，删除最小值，可以注意到可以用堆维护。

第二版思路

使用优先队列维护两相邻点湮灭时间，每次从队列重取点并加入左右点，用双端链表删点。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
struct node{
	long long vl,spd;
	int id,l,r;
	bool tn;
}a[N];
struct pq{
	int x,y;
	long long tm;
	friend bool operator<(pq a,pq b){
		return a.tm>b.tm;
	}
};
int n;
long long ans[N];
priority_queue<pq>q;

__inline long work(int x,int y){ // 任意两点的湮灭时间
	long long t=0;
    t=((a[y].vl-a[x].vl-1)/(a[x].spd+a[y].spd)+1)<<1;
    if(a[x].tn) t--;
    return t;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n;
		while(!q.empty()) q.pop();
		memset(ans,0,sizeof(ans));
		a[0].r=1,a[n+1].l=n;
		for(int i=1;i<=n;i++) a[i].r=i+1,a[i].l=i-1;
		for(int i=1;i<=n;i++) cin>>a[i].vl,a[i].tn=i&1;
		for(int i=1;i<=n;i++) cin>>a[i].spd,a[i].id=i;
        for(int i=a[0].r;a[i].r!=n+1;i=a[i].r){
            int x=i,y=a[i].r;
			long long t=work(x,y);
            q.push({x,y,t});
        }
		while(1){
			auto [x,y,t]=q.top();
			q.pop();
			if(ans[x]||ans[y]) continue; // 若该点对其中一点已经被删，该点对不存在，舍去
			ans[x]=ans[y]=t;
			a[a[x].l].r=a[y].r;
			a[a[y].r].l=a[x].l;
			if(a[0].r==n+1) break;
			if(a[x].l==0||a[y].r==n+1) continue;
			long long nt=work(a[x].l,a[y].r);
			q.push({a[x].l,a[y].r,nt});
		}
		for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
		cout<<"\n";
	}
	return 0;
}