题解 P1442 【铁球落地】
Zachary_260325 · · 题解
建图跑Dijkstra
此题卡我半天...我太菜了...o(╥﹏╥)o
大家可以看看评测记录，有一页多都是我...
本来以为TLE是哪里出了点小问题,然后调了半天，又是不用vector又是玄学优化的...最后看了题解才发现是建图太慢了...
此分界线以上是废话...
思路
-
读入数据，并根据小球初始高度删除高度比小球初始高度高的平台（因为它只能往下滚...）
-
排序平台，来加速建图（因为小球会被第一个覆盖其下落x坐标的板子接住），所以让平台单调递增（或递减）就行...
-
在全部平台排序后，插入小球的初始位置。小球初始位置可以视为在一个高度是y（y表示初始高度），覆盖[x,x]（x表示初始横坐标）范围的（没有宽度的）平台上，让n+1，然后把这个平台保存进去。
-
之后用队列优化建图。因为不是所有平台都会被小球使用，所以不用管多余的平台。
-
建图时从当前的平台左端和右端分别往下找可以承接小球的平台。如果找到平台且高度差小于max（不要忘了...），就记录从小球掉落位置分别到平台两边的距离并连接（不用记录高度差，因为到地面的下落距离一定是y）。如果找不到平台，再去判断地面能不能承接，如果能就连接。建图的时候，为了方便起见，把第i块平台的左端坐标定为i，右端坐标定义为i+n，两个坐标之间没有直接的边连接（因为不需要）。
//P.S. 不要用什么Vector，没有必要...
-
最后跑一遍堆优化的Dijkstra（当然，SPFA在这道题也许更快...如果追求速度还可以学习更强大的最短路算法）
代码
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cctype>
#include<cstring>
#define rint register int
inline int read()
{
rint k=0,c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
k=10*k+c-'0';
c=getchar();
}
return k;
}
struct Q{
int h,x,y;
Q(){}
Q(int _h,int _x,int _y):h(_h),x(_x),y(_y){}
}a[100005];
struct P{
int x,d;
P(){}
P(int _x,int _d):x(_x),d(_d){}
}v[200005][2];
const bool operator <(P a,P b)
{
return a.d>b.d;
}
inline bool cmp(Q a,Q b)
{
return a.h<b.h;
}
std::priority_queue<P> que;
int vis[200005],n,max,x,y;
int main()
{
std::memset(v,-1,sizeof(v));//init
n=read();
max=read();
x=read();
y=read();
for(rint i=1;i<=n;++i)
{
a[i].h=read();
a[i].x=read();
a[i].y=read();
if(a[i].h>y)//delete
{
--n;
--i;
}
}
std::sort(a+1,a+n+1,cmp);
a[++n]=Q(y,x,x);
std::queue<int> tq;
tq.push(n);
while(!tq.empty())
{
int i=tq.front();
tq.pop();
//find left
int mem=0,point=a[i].x,h=a[i].h;
for(int j=i-1;j>=1&&h-max<=a[j].h;--j)
if(a[j].x<=point&&a[j].y>=point)
{
mem=j;
break;
}
int delta=h-a[mem].h;
if(delta<=max)
{
if(mem==0)
v[i][0]=P(0,0);
else
{
v[i][1]=P(n+mem,a[mem].y-point),v[i][0]=P(mem,point-a[mem].x);
if(!vis[mem])
{
tq.push(mem);
vis[mem]=1;
}
}
}
//find right
mem=0,point=a[i].y;
for(int j=i-1;j>=1&&h-max<=a[j].h;--j)
if(a[j].x<=point&&a[j].y>=point)
{
mem=j;
break;
}
delta=h-a[mem].h;
if(delta<=max)
{
if(mem==0)
v[n+i][0]=P(0,0);
else
{
v[n+i][1]=P(n+mem,a[mem].y-point),v[n+i][0]=P(mem,point-a[mem].x);
if(!vis[mem])
{
tq.push(mem);
vis[mem]=1;
}
}
}
}
std::memset(vis,0,sizeof(vis));
que.push(P(n,0));
rint now,d;
while(!que.empty())//Dijkstra
{
now=que.top().x;
d=que.top().d;
que.pop();
if(now==0)
{
printf("%d",d+y);
return 0;
}
if(vis[now])
continue;
vis[now]=1;
for(rint i=0;i<=1;++i)
if(v[now][i].x!=-1&&!vis[v[now][i].x])
que.push(P(v[now][i].x,v[now][i].d+d));
}
return 0;
} 评测结果：130ms/5.63MB
目前RANK1，还算可以了（等那些优化神佬一来就下去了...）