首页 > 试题广场 >

快递机器人

[编程题]快递机器人

热度指数：374 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

图森未来的员工阿伟最新研发了一款快递机器人，他投放了一台机器人在公司办公室中进行试运营。

公司的座位分布比较工整，可以看成一个四分之一平面上的网格图，即所有坐标轴上第一象限中的整点都是一个工位，上下左右相邻的工位间有一条长为1的边。由于阿伟资历比较深，所以坐在了公司的(1, 1)点上。

机器人每天都会从阿伟的座位出发，去n个同事的工位上收快递。每1秒中，机器人可以向x轴正方向，x轴负方向，或者y轴正方向移动1个单位（由于某些技术原因，暂时不允许向y轴负方向移动，同时也不允许移动到公司外，即不允许移动到x坐标小于等于0的位置）。例如，如果当前时刻机器人所在的坐标为(x, y)，下一秒机器人可能可以到达的位置为(x + 1, y)，(x - 1, y)或者(x, y + 1)。当机器人到达某个同事所在的工位时，就会获得要收取的快递，收快递的动作不需要消耗时间。一旦机器人收完所有快递，他就可以立即传送回仓库，把同事们的快递发送出去。

现在阿伟告诉了你今天需要去收快递的所有同事的工位坐标，他希望你可以写一个程序帮他计算一下收完所有快递最少所需要花费的总时间。

输入描述:

输入的第1行包含1个正整数n，表示当天要收货的同事数量。
接下来的n行，每行有两个正整数x和y，表示坐在(x, y)处的同事今天有快递需要收取。保证n个坐标两两不同。

对于 30% 的数据，1 <= n <= 8，1 <= x, y <= 1000；
对于另外 30% 的数据，1 <= n <= 1000，1 <= x, y <= 10⁶，并且保证没有任何超过8个同事位置的y坐标相同。
对于另外 40% 的数据，1 <= n <= 10⁵，1 <= x, y <= 10⁹；

输出描述:

输出只包含一个正整数，为当天收货所需要花费的最少总时间。

示例1

输入

2
3 3
2 2

输出

说明

机器人的最优走法是先从(1, 1)走到(2, 2)，再从(2, 2)走到(3, 3)。两次移动花费的时间都是2，当天收货花费的总时间是4。

算法知识视频讲解

高轲用

#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
 
typedef pair<long long, long long> P;
const int MAXN = 100010;
 
P point[MAXN];
long long lb[MAXN], ub[MAXN];
long long f[MAXN][2];
long long ycost;
 
bool cmp(const P &o1, const P &o2)
{
    return o1.second < o2.second;
}
 
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld%lld", &point[i].first, &point[i].second);
    }
    sort(point, point + n, cmp);
    int to_y = 0, from_y = 0;
    lb[0] = ub[0] = 1;
    for (int i = 0; i < n; i++)
    {
        if (from_y != point[i].second)
        {
            ycost += point[i].second - from_y;
            to_y++;
            lb[to_y] = 1e9;
            from_y = point[i].second;
        }
        lb[to_y] = min(lb[to_y], point[i].first);
        ub[to_y] = max(ub[to_y], point[i].first);
    }
    for (int i = 1; i <= to_y; i++)
    {
        f[i][0] = min(f[i - 1][0] + abs(ub[i] - lb[i - 1]) + (ub[i] - lb[i]), f[i - 1][1] + abs(ub[i] - ub[i - 1]) + (ub[i] - lb[i]));
        f[i][1] = min(f[i - 1][0] + abs(lb[i] - lb[i - 1]) + (ub[i] - lb[i]), f[i - 1][1] + abs(lb[i] - ub[i - 1]) + (ub[i] - lb[i]));
    }
    long long xcost = min(f[to_y][0], f[to_y][1]);
    printf("%lld\n", xcost + ycost - 1);
    return 0;
}

发表于 2021-07-29 15:32:40 回复(0)

牛客277601090号

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
int main(){
    int n;
    scanf("%d",&n);
    p ps[n+1];
    ps[0].first=ps[0].second=1;//起点
    for(int i=1;i<n+1;i++)
        scanf("%d%d",&ps[i].first,&ps[i].second);
    sort(ps,ps+n+1,[](p& p1, p& p2){return p1.second<p2.second;});
    int prey=0,layer=0,costy=0;
    int maxx[n],minx[n];
    maxx[0]=maxx[0]=1;//y为1的所有点的出发点就是x=1
    //统计相同的y中，x的最大与最小值
    for(int i=0;i<n+1;i++){
        int x=ps[i].first;
        int y=ps[i].second;
        if(prey!=y){
            costy+=(y-prey);
            layer++;
            maxx[layer]=0;
            minx[layer]=INT_MAX;
            prey=y;
        }
        minx[layer]=min(minx[layer],x);
        maxx[layer]=max(maxx[layer],x);
    }
    costy--;//由于prey=0，多算了1
    //计算ycost需要动态规划，每种y两个状态:
    //[0]表示最后到达x最小，[1]表示最后达到x最大.
    long long dp[layer+1][2];
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<layer+1;i++){
        dp[i][0]=min(dp[i-1][0]+abs(maxx[i]-minx[i-1]),dp[i-1][1]+abs(maxx[i]-maxx[i-1]))+maxx[i]-minx[i];
        dp[i][1]=min(dp[i-1][0]+abs(minx[i]-minx[i-1]),dp[i-1][1]+abs(minx[i]-maxx[i-1]))+maxx[i]-minx[i];
    }
    long long cost=min(dp[layer][0],dp[layer][1])+costy;
    printf("%lld\n",cost);
}

发表于 2022-08-09 11:10:31 回复(0)

KingFriend

import sys
import gc


class Machine(object):
    @classmethod
    def run(cls, n, xy_list):
        y_list = [xy[1] for xy in xy_list]
        y_list = list(set(y_list))
        y_list.sort()
        item = dict()
        for x, y in xy_list:
            if y in item:
                if item[y]['min'] > x:
                    item[y]['min'] = x
                if item[y]['max'] < x:
                    item[y]['max'] = x
            else:
                item[y] = {'max': x, 'min': x}
        return cls.get_min_step(y_list, item)

    @classmethod
    def get_min_step(cls, y_list, item):
        """
        用递归代码比较好看但是内存超限制了， 于是用了地推
        这个题属于动态规划问题，为了加速弄了缓存: map_info
        从后往前思考这个问题比较容易， 从前往后也行，但是逻辑不清晰
        因为y不能负移动所以从最大y来看，能到达y的点只能有两个
        上一个y 中最小的点与最大的点， 每个都算一下到这两个中点的最短路径
        得出从这两个点出发到终点的最短路径是唯一的，用map_info存下来
        然后逐渐往前递推，也就是上一个y的上个y 他们的最大x与最大y 到达下一个y
        的两个点最短路径是唯一的，然后加上从这个点到终点的距离，不断地推计算
        """
        map_info = dict()
        for i, y in zip(range(len(y_list))[-2::-1], y_list[-2::-1]):
            current1 = (item[y]['min'], y)
            current2 = (item[y]['max'], y)
            next_y = y_list[i+1]
            next_xy1 = (item[next_y]['min'], next_y)
            next_xy2 = (item[next_y]['max'], next_y)
            y_step = abs(next_y - y)
            # 计算 current1 到 next_xy1 与 next_xy2的最短距离
            step1, step2 = cls.get_step(current1, next_xy1, next_xy2, y_list,
                                        y_step, i)
            # 计算 current2 到 next_xy1 与 next_xy2的最短距离
            step3, step4 = cls.get_step(current2, next_xy1, next_xy2, y_list,
                                        y_step, i)
            if i == len(y_list) - 2:
                map_info[current1] = step1 if step1 < step2 else step2
                map_info[current2] = step3 if step3 < step4 else step4
                continue
            next_step1 = map_info[next_xy1]
            next_step2 = map_info[next_xy2]
            step1 = step1 + next_step1
            step2 = step2 + next_step2
            map_info[current1] = step1 if step1 < step2 else step2
            step1 = step3 + next_step1
            step2 = step4 + next_step2
            map_info[current2] = step1 if step1 < step2 else step2

        y = y_list[0]
        current1 = (item[y]['min'], y)
        current2 = (item[y]['max'], y)
        if len(y_list) < 2:
            return abs(y - 1) + (current2[0] - 1)
        step1 = map_info[current1]
        step2 = map_info[current2]
        step1 += abs(y - 1) + (current2[0] - 1) + abs(current1[0] - current2[0])
        step2 += abs(y - 1) + (current2[0] - 1)
        return step1 if step1 < step2 else step2

    @classmethod
    def get_step(cls, current, next_xy1, next_xy2, y_list, y_step, i):
        min_max_step = abs(next_xy1[0] - next_xy2[0])
        if current[0] < next_xy1[0]:
            if i == len(y_list) - 2:
                #  如果已经到头了就不需要重复再走一段了
                step1 = abs(current[0] - next_xy2[0])
            else:
                step1 = abs(current[0] - next_xy2[0]) + min_max_step
        elif current[0] > next_xy2[0]:
            step1 = abs(current[0] - next_xy1[0])
        else:
            if i == len(y_list) - 2:
                step1_1 = abs(current[0] - next_xy1[0]) + min_max_step
                step1_2 = abs(current[0] - next_xy2[0]) + min_max_step
                step1 = step1_1 if step1_1 < step1_2 else step1_2
            else:
                step1 = abs(current[0] - next_xy2[0]) + min_max_step
        # 计算 current 到 next_xy2的最短距离
        if current[0] < next_xy1[0]:
            step2 = abs(current[0] - next_xy2[0])
        elif current[0] > next_xy2[0]:
            if i == len(y_list) - 2:
                #  如果已经到头了就不需要重复再走一段了
                step2 = abs(current[0] - next_xy1[0])
            else:
                step2 = abs(current[0] - next_xy1[0]) + min_max_step
        else:
            if i == len(y_list) - 2:
                step1_1 = abs(current[0] - next_xy1[0]) + min_max_step
                step1_2 = abs(current[0] - next_xy2[0]) + min_max_step
                step2 = step1_1 if step1_1 < step1_2 else step1_2
            else:
                step2 = abs(current[0] - next_xy1[0]) + min_max_step
        return step1 + y_step, step2 + y_step


n = None
index = 0
info = list()
while True:
    index += 1
    if n is None:
        n = int(sys.stdin.readline())
        continue
    x, y = sys.stdin.readline().split(' ')
    info.append((int(x), int(y)))
    if index > n:
        break
gc.collect()
print(Machine.run(n, info))

# 递归代码比较好看， 递推代码多不太好看， 因为内存要求64M就写成递推结构了
# author email: pythonmain@163.com  欢迎学习交流

发表于 2021-08-03 16:07:09 回复(0)

提交观点

问题信息

C++工程师 iOS工程师图森未来安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师安全工程师 c#工程师 2020 大数据开发工程师 Java工程师

上传者：小小

难度：

3条回答 14收藏 2745浏览

通过挑战的用户

想居家的海螺G了

2022-09-24 15:50:10
gph1993

2022-09-22 01:45:10
牛客27760...

2022-08-09 11:10:02
牛客84916...

2022-08-08 03:13:01
牛客31718...

2022-08-03 21:46:27

快递机器人

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题