主页 / 问题 / 1539831
Accepted
Nymos
Asked:2023-09-09 23:13:20 +0000 UTC2023-09-09 23:13:20 +0000 UTC

Python 任务：“绘制立方体”

  • 772

问题是当输入数字11 4和1 1 2 1 2 2 1 4 4 2 4

结果显示：22，但是应该是21！

任务

胶带上排列着一排立方体n。每个立方体必须涂上特定的颜色。所有颜色的编号从1到k。绘画是由机器人完成的，它可以从一个立方体移动到另一个立方体，并将选定的立方体涂上特定的颜色。从结构上讲，机器人的设计使得它可以首先按颜色编号 绘制立方体1，然后按颜色编号，2依此类推。选择数字较大的颜色后，您将无法返回数字较小的颜色。

除此之外，机器人还花时间在立方体之间移动。我们假设在两个相邻的立方体之间移动正好需要одну секунду。需要为机器人创建一系列动作，其中在立方体之间移动所花费的时间将尽可能少。

在此输入图像描述

让我们看一下图中的示例。有一些11立方体需要用 3 种颜色涂上数字1、2和4。

图中机器人的运动如下：它将开始为立方体1上的数字着色，然后为 和立方体着色。这需要他。之后，机器人会将颜色更改为数字并去绘制立方体，然后转身去绘制。这需要他。接下来，机器人会将颜色更改为，因为 中没有需要绘制的立方体，并且将在和之后去绘制立方体。这需要他。结果，机器人将花费。12476 секунд26531011 секунд4311984 секунды21 секунду

请注意，根据问题的情况，机器人只能在选择颜色 2 之后选择颜色 4。机器人还有其他可能的移动路线，但需要更长的时间。

编写一个程序，找出机器人在立方体之间移动的最小可能总时间，直到它们全部被涂上颜色。最初，机器人位于立方体编号1。

输入格式。

第一行的输入是两个自然数n，以及k- 立方体的数量和颜色的数量，1≤n，k≤100000第二行的输入是n自然数1,2,…,c1,c2,…,cn，其中-该立方体ci所需的颜色， 。i1≤ci≤k

输出格式

打印一个数字——在立方体之间移动的最短可能时间。

这是我的代码：

def min_robot_movement(n, k, colors):
    positions = [[] for _ in range(k)]
    current_position = 1
    total_time = 0

    for i in range(len(colors)):
        positions[colors[i] - 1].append(i + 1)

    for color_positions in positions:
        color_positions.sort()
        for position in color_positions:
            total_time += abs(current_position - position)
            current_position = position

    return total_time

# Пример использования
n, k = map(int, input().split())
colors = list(map(int, input().split()))

result = min_robot_movement(n, k, colors)
print("Минимальное время перемещения робота:", result)
python

2 个回答

  1. Best Answer

    你的错误是所有颜色都是从左到右处理的。例如2 2 1，机器人会这样画：它会向右走到尽头，再回到左边，画出两个。虽然只有五步，但四步就足够了。

    请注意，在一组相同颜色的立方体中，只留下最左边和最右边的立方体就足够了。它们之间的立方体不影响移动时间。如果机器人位于位置p，则它可以通过两种方式绘制该组：p -> 左立方体 -> 右立方体和p -> 右立方体 -> 左立方体。因此，在对组进行涂漆之后，机器人将位于组的末端之一。对于每一端，我们都会记住到达该位置的最少步数。最后，我们选择两个位置的最小距离。

    复杂度O(n + k)。

    n, k = map(int, input().split())

ranges = [[n + 1, 0] for _ in range(k)]
for i, c in enumerate(map(int, input().split()), start=1):
    r = ranges[c - 1]
    r[0] = min(i, r[0])
    r[1] = max(i, r[1])

ends = (0, 1), (0, 1)
for lo, hi in ranges:
    if lo <= hi:
        ends = (
            (min(d + abs(p - hi) + (hi - lo) for d, p in ends), lo),
            (min(d + abs(p - lo) + (hi - lo) for d, p in ends), hi)
        )
print(min(d for d, _ in ends))
    • 5

  2. 要绘制相同颜色的立方体，您需要从最左边到最右边（反之亦然，也移动）。它起着从哪一侧接近下一个颜色的作用。我们开始从末端寻找最短路径，因为沿剩余颜色的路径不依赖于先前颜色的位置：以较小者为准，转到下一个颜色的左侧立方体（然后我们将从右侧的立方体），或右侧的立方体（然后我们将从左侧的立方体走得更远）。由于我们不需要从最后一个立方体移动到任何地方，因此我们可以从任何方向接近最后一个颜色。

    n, k = map(int, input().split())
ci = sorted(zip(map(int, input().split()), range(n)), key = lambda c: c[0]) # сопоставляем каждому кубику номер, а потом сортируем по цветам
cc = [(0, 0)]
cR = cL = ci[0]
for i in range(1, n):
    if ci[i][0] != cL[0]:
        cc.append((cL[1], cR[1]))
        cL = ci[i]
    cR = ci[i]
cc.append((cL[1], cR[1])) # получили список левого и правого кубиков для каждого цвета
sl = sr = 0
for i in range(len(cc) - 1, 0, -1):
    r = cc[i][1] - cc[i][0]
    nl = min(abs(cc[i][0] - cc[i - 1][1]) + sl, abs(cc[i][1] - cc[i - 1][1]) + sr)
    nr = min(abs(cc[i][0] - cc[i - 1][0]) + sl, abs(cc[i][1] - cc[i - 1][0]) + sr)
    sl, sr = nl + r, nr + r
print(min(sl, sr))

    这里的难点是“排序数组n”+“遍历数组n”+“遍历数组l(l<=k)”。

    • 1

相关问题