首页 > 试题广场 > 车队管理
[编程题]车队管理
  • 热度指数:323 时间限制: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个位置。
解题思路:
·如果只考虑往外扩张的车辆,发现只能扩展log层,猜想车辆的活动半径不会很大,打表发现是个类似圆形的图形,也就说明车辆的移动直径是根号n级别的,把横纵坐标都+500,可以直接用数组来模拟
·会发现车辆的移动顺序是无关的,假如一个方格内有16辆车,一次移动8辆和一次移动16辆是等价的,模拟的时候就可以把尽可能多的车移动出去。

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define Please return
#define AC 0
using namespace std;
template <class T>
void read(T &val) { T x = 0; T bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }

int n,m;
queue<pii>qq[2];
int mp[1100][1100],nw;
void move(){
    while(!qq[nw].empty()){
        auto tp = qq[nw].front();qq[nw].pop();
        if(mp[tp.first][tp.second]<8) continue;
        int add = mp[tp.first][tp.second]/8;
        fo(i,-1,1){
            fo(j,-1,1){
                if(i==0&&j==0) continue;
                mp[tp.first+i][tp.second+j]+=add;
                if(mp[tp.first+i][tp.second+j]>=8) qq[nw^1].push({tp.first+i,tp.second+j});
            }
        }
        mp[tp.first][tp.second]%=8;
    }
    nw^=1;
}

int sum[1100][1100];
void change(int &x){//打表发现,半径不超过100
    x = min(x,100);x = max(x,-100);
    x+=500;
}
int main(){
    read(n);read(m);
    if(n>=8) qq[0].push({500,500});
    mp[500][500] = n;
    while(!qq[nw].empty()){
        move();
    }
    fo(i,1,1000){
        fo(j,1,1000){
            sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
        }
    }
    while(m--){
        int x1,y1,x2,y2;read(x1);read(y1);read(x2);read(y2);
        change(x1);change(y1);change(x2);change(y2);
        printf("%d\n",sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]);
    }
    Please AC;
}


编辑于 2021-01-27 21:20:54 回复(0)
用最简单的思路去进行模拟,但是内存超了,只通过了70%
import sys
sys.setrecursionlimit(1000000)

def distribute_car(n, intial_loc, dic):
    if n < 8:
        # 如果目前车的数量n小于8,直接该网格内的车数为n即可
        dic[tuple(intial_loc)] = n
        return
    else:
        dic[tuple(intial_loc)] = n
        # 否则需要向周围的8个方向移动车
        every_num = n // 8
        surround = list()
        surround.append([intial_loc[0] + 0, intial_loc[1] + 1])
        surround.append([intial_loc[0] + 0, intial_loc[1] - 1])
        surround.append([intial_loc[0] + 1, intial_loc[1] + 0])
        surround.append([intial_loc[0] - 1, intial_loc[1] + 0])
        surround.append([intial_loc[0] + 1, intial_loc[1] - 1])
        surround.append([intial_loc[0] - 1, intial_loc[1] + 1])
        surround.append([intial_loc[0] + 1, intial_loc[1] + 1])
        surround.append([intial_loc[0] - 1, intial_loc[1] - 1])
        for grid in surround:
            # 周围位置车数增加
            if tuple(grid) not in dic:
                dic[tuple(grid)] = every_num
            else:
                dic[tuple(grid)] += every_num
            # 中心位置车数减少
            dic[tuple(intial_loc)] = dic[tuple(intial_loc)] - every_num
        # 记录超过8辆车的单元格
        temp_dic = dict()
        for grid in dic.keys():
            if dic[grid] >= 8:
                temp_dic[grid] = dic[grid]
        # 这些网格再进行车分配
        for grid in temp_dic.keys():
            distribute_car(dic[grid], grid, dic)

# 计算车数量
def count_car(grid, dic):
    x1, y1, x2, y2 = grid[0], grid[1], grid[2], grid[3]
    count = 0
    for pos in dic:
        if pos[0] >= x1 and pos[0] <= x2 and pos[1] >= y1 and pos[1] <= y2:
            count += dic[pos]
    return count

n, m = list(map(int, input().split()))
queries = list()
# 每个元素是一个列表,具有4个元素,分别是两组坐标
for _ in range(m):
    queries.append(list(map(int, input().split())))
dic = dict()
# 分配车的位置
distribute_car(n, [0, 0], dic)
for query in queries:
    print(count_car(query, dic))


发表于 2020-12-11 18:11:46 回复(0)

应注意n大小,最后有车格子组成的图形大小是有限的且是正方形。根据对称性,先算1/8小块的车流量,然后再映射到大的地图上。

#include
#include
using namespace std;
const int ms = 128;
void print1(int m[ms][ms], int s = 8) {
    for(int i=-s; i<=s; i++) {
        for(int j=-s; j<=s; j++)
            if(abs(i)<=abs(j)) cout << m[abs(i)][abs(j)] << ' ';
            else cout << m[abs(j)][abs(i)] << ' ';
        cout << endl;
    }
    cout << "----------------" << endl;
}
void print2(int m[ms*2][ms*2], int s = 8) {
    for(int i=ms-s; i<=ms+s; i++) {
        for(int j=ms-s; j<=ms+s; j++)
            cout << m[i][j] << ' ';
        cout << endl;
    }
    cout << "----------------" << endl;
}
void weight(int bff[ms][ms], int x, int y, int f = 0) {
    if(x y) return;
    if(x==0 && y==0) bff[x][y] += 4;
    else if(x==0 && !(f==1)) bff[x][y] += 2;
    else if(x==y && !(f==2)) bff[x][y] += 2;
    else bff[x][y] += 1;
}
void trans(int bff[ms][ms], int x, int y) {
    if(x==0 && y==1) bff[x][y] -= 6;
    else if(y-x==1) bff[x][y] -= 7;
    else bff[x][y] -= 8;
    weight(bff, x-1, y-1, x==y?2:0);
    weight(bff, x-1, y);
    weight(bff, x-1, y+1);
    weight(bff, x, y-1, x==0?1:0);
    weight(bff, x, y+1, x==0?1:0);
    weight(bff, x+1, y-1);
    weight(bff, x+1, y);
    weight(bff, x+1, y+1, x==y?2:0);
}
void update(int m[ms][ms], bool & noUpdate) {
    static int s = 1;
    int bff[ms][ms];
    noUpdate = true;
    memset(bff, 0, sizeof(bff));
    if(m[0][0]>=8) {
        noUpdate = false;
        bff[0][0] -= 8; bff[0][1] ++;
        bff[1][1] ++;
    }
    for(int i=0; i < s; i++)
        for(int j=i; j < s; j++)
        if(m[i][j]>=8 && !(i==0 && j==0)) {
            noUpdate = false;
            trans(bff, i, j);
        }
    if(bff[0][s]>0) s++;
    for(int i=0; i< s; i++)
        for(int j=i; j < s; j++)
        m[i][j] += bff[i][j];
}
const int c = 100;
void dev(int & x, int offset = 0) {
    x += offset;
    if(x>c) x = c;
    else if(x<-c) x = -c;
    x += ms;
}
int main() {
    int m[ms][ms];
    int n, q;
    memset(m, 0, sizeof(m));
    cin >> n >> q;
    bool noUpdate = false;
    m[0][0] = n;
    while(!noUpdate) update(m, noUpdate);
    int mm[ms*2][ms*2];
    int sum[ms*2][ms*2];
    memset(mm, 0, sizeof(mm));
    memset(sum, 0, sizeof(sum));
    for(int i=0; i<= c; i++)
        for(int j=i; j <= c; j++) {
            mm[ms+i][ms+j] = m[i][j];
            mm[ms+i][ms-j] = m[i][j];
            mm[ms-i][ms+j] = m[i][j];
            mm[ms-i][ms-j] = m[i][j];
            mm[ms+j][ms+i] = m[i][j];
            mm[ms+j][ms-i] = m[i][j];
            mm[ms-j][ms+i] = m[i][j];
            mm[ms-j][ms-i] = m[i][j];
        }
    for(int i=ms-c; i<= ms+c; i++)
        for(int j=ms-c; j <= ms+c; j++) {
            sum[i][j] = mm[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    //print2(mm);
    //print2(sum);
    while(q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        dev(x1,-1); dev(y1,-1); dev(x2); dev(y2);
        //cout << " " << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
        //cout << " " << sum[x1][y1] << " " << sum[x2][y2] << " " << sum[x1][y2] << " " << sum[x2][y1] << endl;
        cout << sum[x1][y1] - sum[x1][y2] - sum[x2][y1] + sum[x2][y2] << endl;
    }
}
发表于 2020-11-09 23:47:43 回复(0)
70%
import sys

lines = sys.stdin.readlines()

num_all, query_all = lines[0].strip().split()
num_all = int(num_all)
query_all = int(query_all)

DICT_ALL = {0: {0: int(num_all)}}

def add_num_to_dict_all(temp_x, temp_y):
    x_lowwer = temp_x - 1
    y_lowwer = temp_y - 1
    x_upper = temp_x + 1
    y_upper = temp_y + 1
    for x in [x_lowwer, temp_x, x_upper]:
        if x not in DICT_ALL:
            DICT_ALL[x] = {}
        for y in [y_lowwer, temp_y, y_upper]:
            if x == temp_x and y == temp_y:
                continue
            if y not in DICT_ALL[x]:
                DICT_ALL[x][y] = 1
            else:
                DICT_ALL[x][y] += 1
                if DICT_ALL[x][y] >= 8:
                    BIG_LIST.append((x, y))

BIG_LIST = [(0, 0)]

while BIG_LIST:
    for x, y in BIG_LIST.copy():
        if DICT_ALL[x][y] >= 8:
            add_num_to_dict_all(x, y)
            DICT_ALL[x][y] -= 8
            if DICT_ALL[x][y] < 8:
                BIG_LIST.remove((x, y))
        else:
            BIG_LIST.remove((x, y))

query_all = [list(map(int, line.strip().split())) for line in lines[1:] if line.strip()]
for item in query_all:
    sum = 0
    for x_key, x_value in DICT_ALL.items():
        if item[0] <= x_key <= item[2]:
            for y_key, y_value in x_value.items():
                if item[1] <= y_key <= item[3]:
                    sum += DICT_ALL[x_key][y_key]
    print(sum)

超时了

发表于 2020-08-07 15:45:04 回复(1)
n, q = [int(i) for i in input().split(" ")]
moving = 1 if n > 8 else 0
l = n
carMap = [[0]*(2*l+1) for _ in range(2*l+1)]
carMap[l][l] = n
while moving:
    moving = 0
    carMove = [[0]*(2*l+1) for _ in range(2*l+1)]
    for i in range(2*l+1):
        for j in range(2*l+1):
            if carMap[i][j] > 8:
                moving = 1
                for p in [-1,0,1]:
                    for qi in [-1,0,1]:
                        carMove[i+p][j+qi] += 1
                carMove[i][j] -= 9
    if moving:
        for i in range(2*l+1):
            for j in range(2*l+1):
                carMap[i][j] += carMove[i][j]


for k in range(q):
    x1,y1,x2,y2 = [int(i) for i in input().split(" ")]
    x1 = min(max(x1,-l),l)
    y1 = min(max(y1,-l),l)
    x2 = min(max(x2,-l),l)
    y2 = min(max(y2,-l),l)
    print(sum(list(map(sum, [i[l+x1:l+x2+1] for i in carMap[l+y1:l+y2+1]]))))
    # print(sum(carMap[l+y1:l+y2+1][l+x1:l+x2+1]))
30% 通过 其余超时
发表于 2020-12-09 22:00:35 回复(0)
60% 超时了
from collections import Counter
from sys import stdin
 
first_line = stdin.readline().strip()
N, Q = list(map(int, first_line.split(" ")))
 
car_list = [[0, 0] for _ in range(N)]
directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
 
 
def positionlist2move(car_list):
    counter = Counter([tuple(x) for x in car_list])
    return [x[0] for x in counter.most_common() if x[1] >= 8]
 
 
def movecar_batch(cars):
    assert len(cars) == 8, len(cars)
    for car, d in zip(cars, directions):
        car[0] += d[0]
        car[1] += d[1]
 
 
while True:
    positions2move = positionlist2move(car_list)
    if len(positions2move) == 0:
        break
    for position in positions2move:
        cars = [x for x in car_list if x == list(position)][:8]
        movecar_batch(cars)
 
for _ in range(Q):
    x1, y1, x2, y2 = list(map(int, stdin.readline().strip().split(" ")))
    avaible_cars = [x for x in car_list if x1 <= x[0] <= x2 and y1 <= x[1] <= y2]
    print(len(avaible_cars))

发表于 2020-12-03 17:32:15 回复(0)
def descri_car(n, intial_loc, dict):

    if n < 8:
        dict[tuple(intial_loc)] = n
        return
    else:
        every_num = n // 8
        sur = list()
        sur.append([intial_loc[0] + 0,intial_loc[1] + 1])
        sur.append([intial_loc[0] + 0,intial_loc[1] + -1])
        sur.append([intial_loc[0] + 1,intial_loc[1] + 0])
        sur.append([intial_loc[0] + -1,intial_loc[1] + 0])
        sur.append([intial_loc[0] + 1,intial_loc[1] + -1])
        sur.append([intial_loc[0] + -1,intial_loc[1] + 1])
        sur.append([intial_loc[0] + 1,intial_loc[1] + 1])
        sur.append([intial_loc[0] + -1,intial_loc[1] + -1])
        dict[tuple(intial_loc)] = n
        for i in range(8):
            if not dict.get(tuple(sur[i])):
                dict[tuple(sur[i])] = every_num
                dict[tuple(intial_loc)] = dict[tuple(intial_loc)] - every_num
            else:
                dict[tuple(sur[i])] += every_num
                dict[tuple(intial_loc)] = dict[tuple(intial_loc)] - every_num
        temp_dic = {}
        for i in dict.keys():
            if dict[i] >= 8:
                temp_dic[i] = dict[i]
                # print(temp)
        for i in temp_dic.keys():
            temp = dict[i]
            descri_car(temp, i, dict)

def car_number(loc, dict):
    x1,y1,x2,y2 = loc[0], loc[1], loc[2], loc[3]
    key = list(dict.keys())
    sum = 0
    for i in key:
        if i[0] >= x1 and i[0] <= x2 and i[1] >= y1 and i[1] <= y2:
            sum += dict[i]
    return sum


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    i = 0
    ins_sym = list()
    # 每个元素是一个列表,具有4个元素,分别是两组坐标
    while i < m:
        data = list(map(int, input().split()))
        ins_sym.append(data)
        i += 1
    # 两个函数,一个分配位置,一个计算数目
    intial_loc = [0, 0]
    dict = {}
    descri_car(n, intial_loc, dict)
    for i in ins_sym:
        print(car_number(i, dict))

发表于 2020-07-23 18:20:31 回复(0)