-2

与えられた問題:

一定数の兵士がいます。

各兵士には特定のランクがあります (将校、軍曹などもいます)。今、彼らは何人かの男を殺そうとしています。

弾薬の量が限られています。ランクに応じて、各人に弾薬箱が与えられます。兵士たちは一直線に並んでいます。

ランクの低い人が隣にいる場合、ランクの高い人により多くの弾薬を与えなければなりません。

各人に少なくとも 1 つの箱を渡す必要があります。

例: を表すために 1 から上の数字を使用しますrank: 4 2 3 2 2 1 3 6。同等の弾薬箱は次のとおり2 1 2 1 2 1 2 3です。

弾薬のリストを作成するための最速の方法は、最初の 3 つのランクを取得し、それらを相互に比較することです (つまり、例から を選択し4 2 3ます)。次に、1 つ増やして (つまり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

0

ヒント: この場合、山と谷を定義する必要があります。ピークは、隣接する要素 >= です。谷は要素 <= その隣人です。

谷に 1 つのボックスを割り当てます。

山と谷は交互になります。頂点に達するボックスの数 = 前の谷と次の谷からの距離の大きい方。

于 2013-10-31T16:13:23.603 に答える