-2

给定一个问题：

你有一定数量的士兵。

每个士兵都有一个给定的等级（有些是军官、中士等）。现在他们要去杀了一些人。

你的弹药数量有限。根据等级，每个人都会得到一盒弹药。士兵们站成一条直线。

如果一个较低等级的人在他旁边，则必须给较高等级的人更多的弹药。

每个人必须至少得到一个盒子。

示例：使用从 1 向上的数字来表示rank: 4 2 3 2 2 1 3 6. 等效的弹药箱是：2 1 2 1 2 1 2 3.

我想出弹药清单的最快方法是取前三个等级并将它们相互比较（即从示例中，我选择4 2 3）。接下来我增加一（即2 3 2）并再次进行比较。显然，这需要很多时间。有没有更快的方法？

注意：同级别的士兵并排站在一起并不在乎每个人有多少弹药。

soldier_num = int(input())
i = 0
rating_array = []
ammo_array = []
can_can = soldier_num
while(i < soldier_num):
    rating_array.append(int(input()))
    ammo_array.append(1)
    i += 1
i = 0
while(i < soldier_num):
    if(i == 0):
        if((rating_array[i] > rating_array[i+1]) and (ammo_array[i] <= ammo_array[i+1])):
            ammo_array[i] += 1
            i = i-1
            can_can += 1

    if(0<i<(soldier_num-1)):
        if((rating_array[i] > rating_array[i+1]) and (ammo_array[i] <= ammo_array[i+1])):
            ammo_array[i] += 1
            i = i-1
            can_can += 1

        elif((rating_array[i] > rating_array[i-1]) and (ammo_array[i] <= ammo_array[i-1])):
           ammo_array[i] += 1
            i = i-1
            can_can += 1

        elif((rating_array[i] < rating_array[i-1]) and (ammo_array[i] >= ammo_array[i-1])):
            ammo_array[i-1] += 1
            i = i-1
            can_can += 1

        elif((rating_array[i] < rating_array[i+1]) and (ammo_array[i] >= ammo_array[i-1])):
            ammo_array[i+1] += 1
            i = i-1
            can_can += 1

    i += 1
    if(i == (soldier_num-1)):
        if((rating_array[i] > rating_array[i-1]) and (ammo_array[i] <= ammo_array[i-1])):
            ammo_array[i] += 1
            can_can += 1



print(can_can)
4

2 回答 2

1

每个数字有 4 个可能的类别：

  • 两个邻居都更高（山谷）
  • 两个邻居都较低（峰值）
  • 左高右低（下坡）
  • 右高左低（上坡）

当您在寻找谷值和0寻找峰值时，将越界索引计数为无穷大。既然你说“同等级的邻居不关心”，那你就可以用同样的方法来算了。

首先将所有的山谷减少到1。这应该很简单。

要减少上坡元素，请遍历数组并将它们减少到left+1.

为了减少下坡的，向后迭代并将它们减少到right+1.

最后，峰值降低到更高的邻居，加一。

对于您的示例：

4 2 3 2 2 1 3 6    < original

4 1 3 1 2 1 3 6    < valleys reduced
4 1 3 1 2 1 2 3    < uphill reduced
2 1 3 1 2 1 2 3    < downhill reduced
2 1 2 1 2 1 2 3    < peaks reduced
于 2013-10-31T16:29:59.053 回答
0

提示：在这种情况下，您必须定义峰和谷。峰是 >= 其邻居的元素。山谷是元素<=它们的邻居。

将 1 个框分配给山谷。

峰谷交替出现。到达峰值的框数 = 与前一个山谷和下一个山谷的距离较大。

于 2013-10-31T16:13:23.603 回答