首页 > 试题广场 >

车队管理

[编程题]车队管理
  • 热度指数:563 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小马智行(Pony.ai)在广州南沙区有一支稳定运营的自动驾驶车队,可以将南沙区的地图看做一个二维的网格图,小马智行的广州office在(0, 0)位置。
公司现在有n台车,每天会按如下规则从围绕南沙区进行路测:
1. 初始n辆车都在公司。
2. 放眼整个南沙地图,每过一分钟, 若有一个网格的车数大于等于8, 则这个网格同时会有8辆车分别前往上,下,左,右,左上,左下,右上,右下的网格,不停执行该步骤直到所有的车辆的位置都固定不变。
作为小马智行车辆控制中心的一员, 你需要监管车辆运营的情况, 你需要等到所有车辆的位置固定之后,进行q次抽样统计, 每次需要统计出以(x_1, y_1)为左下角,以(x_2, y_2)为右上角的矩形范围内车辆的车辆的数目。


输入描述:
第一行为n和q, 分别代表初始office内的车辆数和抽样的次数。
之后q行,每行包含4个变量x_1, y_1, x_2, y_2 含义见题目描述。
后, 进行q次抽样,每次查询以(x_1, y_1)为左下角,以(x_2, y_2)为右上角的矩形范围内车辆的数目。



输出描述:
输出q次抽样的结果,每次结果独占一行。
示例1

输入

8 2
0 0 0 0
-1 -1 1 1

输出

0
8

说明

第0分钟所有车辆都在office处。

第1分钟及以后, 8辆车分别在(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)这8个位置。
头像 萝卜朝天椒
发表于 2021-01-27 21:20:19
解题思路:·如果只考虑往外扩张的车辆,发现只能扩展log层,猜想车辆的活动半径不会很大,打表发现是个类似圆形的图形,也就说明车辆的移动直径是根号n级别的,把横纵坐标都+500,可以直接用数组来模拟·会发现车辆的移动顺序是无关的,假如一个方格内有16辆车,一次移动8辆和一次移动16辆是等价的,模拟的时 展开全文

热门推荐

通过挑战的用户