传送门
题意
给出 \(n\) 个坐标轴上的点,把他们标记, 每次询问一个 \((x, y)\), 求与该点曼哈顿距离最近的没有被标记的点
题解
不太难, 就用暴力做法了
考虑到一个点到它最近的非标记点的路径,不会同时存在向右和向左, 也不会同时存在向上向下
假如限制只能向下和向右走的话,那么显然可以dp且没有后效性, 如果存在一个答案在右下方,那么这样dp是对的
不然的话,答案要么在左上,要么左下, 要么右上,4遍记忆化即可
看似暴力,实际理论复杂度\(O(n)\), 虽然我常数及其大, 哦不对我摆烂用了map,寄!
实现
考场暴力代码
#include
#include
#include