Luogu P4088 [USACO18FEB]Slingshot P 题解

Preface

题目链接

rua!调了半天发现原来是 $id$ 的问题。。。

Description

有一个数轴,上面有 $n$ 个传送门,使用第 $i$ 个传送门,你可以从 $x_i$​ 走到 $y_i$​,花费的时间为 $t_i$ 秒。你的速度为 $1$ 格/秒,有 $m$ 次询问,每次你要从 $a_i$​ 走到 $b_i$​,最多使用一次传送门,问最少需要多少秒。

$1\leq n ,m \leq 10^5 ,0 \leq a_i ,b_i \leq 10^9$

Solution

显然,对于第 $j$ 个询问使用第 $i$ 个传送门,需要 $|x_i -a_j |+|y_i – b_j|+t_i$ 秒的时间。

考虑这个绝对值很像曼哈顿距离,于是可以把这道题转化:

平面上有 $n$ 个点,第 $i$ 个点位于 $(x_i,y_i)$,有点权为 $t_i$。有 $m$ 次询问,要求与 $(a_i,b_i)$ 的曼哈顿距离加上点权最小的点。

所以直接二维数点,暴力将绝对值拆开,分四类讨论即可。

Code


// Problem: P4088 [USACO18FEB]Slingshot P
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4088
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Auther: yzxoi
// Site: yzxoi.top 

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}
using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}
using namespace FastIO;
Cn int N=100010;
int n,m,lsh[2][N<<1];
LL tr[N<<4],Ans[N<<1];
struct node{int x,y,t,id;}a[N<<1];
I int cmp(Cn node& x,Cn node& y){return x.x<y.x||(x.x==y.x&&x.y<y.y);}
I void update(int x,int l,int r,int pos,LL v){
	if(l==r) return void(tr[x]=min(tr[x],v));
	int mid=l+r>>1;
	if(pos<=mid) update(x<<1,l,mid,pos,v);
	else update(x<<1|1,mid+1,r,pos,v);
	tr[x]=min(tr[x<<1],tr[x<<1|1]);
}
I LL query(int x,int l,int r,int L,int R){
	if(L<=l&&r<=R) return tr[x];
	int mid=l+r>>1;LL res=2e18;
	if(L<=mid) res=min(res,query(x<<1,l,mid,L,R));
	if(R>mid) res=min(res,query(x<<1|1,mid+1,r,L,R));
	return res;
}
int main(){
	read(n,m);for(RI i=1;i<=n;i++) a[i].id=-1,read(a[i].x,a[i].y,a[i].t),lsh[0][++lsh[0][0]]=a[i].x,lsh[1][++lsh[1][0]]=a[i].y;
	for(RI i=n+1;i<=m+n;i++) a[i].id=i-n,read(a[i].x,a[i].y),Ans[a[i].id]=abs(a[i].x-a[i].y),lsh[0][++lsh[0][0]]=a[i].x,lsh[1][++lsh[1][0]]=a[i].y;
	for(RI i=0;i<2;i++) sort(lsh[i]+1,lsh[i]+1+lsh[i][0]),lsh[i][0]=unique(lsh[i]+1,lsh[i]+1+lsh[i][0])-lsh[i]-1;
	for(RI i=1;i<=m+n;i++) a[i].x=lower_bound(lsh[0]+1,lsh[0]+1+lsh[0][0],a[i].x)-lsh[0],a[i].y=lower_bound(lsh[1]+1,lsh[1]+1+lsh[1][0],a[i].y)-lsh[1];
	sort(a+1,a+m+n+1,cmp);
	memset(tr,127,sizeof(tr));for(RI t,i=1;i<=m+n;i++)
		if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n+m,1,a[i].y)+lsh[0][a[i].x]+lsh[1][a[i].y]);
		else update(1,1,n+m,a[i].y,-lsh[0][a[i].x]-lsh[1][a[i].y]+a[i].t);
	memset(tr,127,sizeof(tr));for(RI i=m+n;i>=1;i--)
		if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n+m,a[i].y,n+m)-lsh[0][a[i].x]-lsh[1][a[i].y]);
		else update(1,1,n+m,a[i].y,lsh[0][a[i].x]+lsh[1][a[i].y]+a[i].t);
	memset(tr,127,sizeof(tr));for(RI i=1;i<=m+n;i++)
		if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n+m,a[i].y,n+m)+lsh[0][a[i].x]-lsh[1][a[i].y]);
		else update(1,1,n+m,a[i].y,-lsh[0][a[i].x]+lsh[1][a[i].y]+a[i].t);
	memset(tr,127,sizeof(tr));for(RI i=m+n;i>=1;i--)
		if(~a[i].id) Ans[a[i].id]=min(Ans[a[i].id],query(1,1,n+m,1,a[i].y)-lsh[0][a[i].x]+lsh[1][a[i].y]);
		else update(1,1,n+m,a[i].y,lsh[0][a[i].x]-lsh[1][a[i].y]+a[i].t);
	for(RI i=1;i<=m;i++) writeln(Ans[i]);
	return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇