首页 > 试题广场 >

车队管理

[编程题]车队管理

热度指数：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个变量, , ,  含义见题目描述。
后， 进行q次抽样，每次查询以为左下角，以为右上角的矩形范围内车辆的数目。

输出描述:

输出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个位置。

算法知识视频讲解

Java

pein531

模拟+二维前缀和

用最简单的思路去进行模拟，但是要探索一下测试数据究竟会给出多大的网格，最终测试得到结论：当从原点向四周延伸100的距离时能够覆盖测试数据的极限。感觉如果是笔试场合不给出bad case的话基本是做不出来的。

import java.io.*;
import java.util.*;

public class Main {
    private static int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
    private static int[] dy = {0, 0, -1, 1, -1, 1, 1, -1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int q = Integer.parseInt(params[1]);
        int offset = 100, N = (offset << 1)|1;
        int[][] grid = new int[N][N];
        grid[offset][offset] = n;
        boolean change = true;
        while(change){
            change = false;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    if(grid[i][j] >= 8){
                        change = true;
                        // 若干波8辆车分散到8个方向
                        for(int k = 0; k < 8; k++){
                            int x = i + dx[k];
                            int y = j + dy[k];
                            if((0 <= x && x < N) && (0 <= y && y < N)){
                                grid[x][y] += grid[i][j] / 8;
                            }
                        }
                        grid[i][j] %= 8;
                    }
                }
            }
        }
        // 矩阵前缀和
        int[][] prevSum = new int[N][N];
        for(int x = 0; x < N; x++) {
            for(int y = 0; y < N; y++) {
                if(x == 0 && y == 0) {
                    prevSum[x][y] = grid[x][y];
                }else if(x == 0) {
                    prevSum[x][y] = grid[x][y] + prevSum[x][y - 1];
                }else if(y == 0) {
                    prevSum[x][y] = grid[x][y] + prevSum[x - 1][y];
                }else{
                    prevSum[x][y] = grid[x][y] + prevSum[x - 1][y] + prevSum[x][y - 1] - prevSum[x - 1][y - 1];
                }
            }
        }
        // 查询
        while(q-- > 0){
            params = br.readLine().split(" ");
            int x1 = Integer.parseInt(params[0]);
            int y1 = Integer.parseInt(params[1]);
            int x2 = Integer.parseInt(params[2]);
            int y2 = Integer.parseInt(params[3]);
            // 卡边界
            x1 = Math.max(offset + x1, 1);
            y1 = Math.max(offset + y1, 1);
            x2 = Math.min(offset + x2, N - 1);
            y2 = Math.min(offset + y2, N - 1);
            if(x1 > x2 || y1 > y2){
                System.out.println(0);
            }else{
                System.out.println(prevSum[x2][y2] - prevSum[x1 - 1][y2] - prevSum[x2][y1 - 1] + prevSum[x1 - 1][y1 - 1]);
            }
        }
    }
}

编辑于 2022-04-18 16:51:07 回复(0)