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

暂无评论

发送评论 编辑评论


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