橋梁的長度和承載能力是已知的。每輛火車的貨車都有給定的長度和重量。程式必須確定列車是否可以安全過橋，即同時在橋上的貨車總重量是否超過橋的承載能力。為安全起見，如果貨車的任何部分在橋上，我們將計算該貨車的整個重量來計算當時的總重量。
輸入格式：
第一個輸入行包含兩個整數：橋的長度和承載能力。
以下輸入行包含一系列對，按順序指示每個貨車的長度和重量。每輛貨車的長度和重量將始終出現在同一行上。每個輸入行的長度最多為 200 個字符。
輸出：
如果火車可以安全過橋，請寫下數字-1。否則，請寫出導致重量超過橋梁承載能力的第一輛貨車的編號。貨車從 1 開始編號。
示例輸入 #1：
10 100
10 90 10 10 9 80 1 10 9 10 9 80
5 10 5 10
1 10 1 10 1 10 1 10 1 40
輸出：
-1
示例輸入 #2：
7 20
3 4 3 5
3 5 3 7
3 7 3 7
3 6
輸出：
4
還有一些例子：
輸入：
5 10
5 5 5 5 5 5 5 5 5 5 5 100 5 100 5 100
輸出：
6
我的代碼是
def bridge(p, k, n):
if p or n == 0:
print(-1)
else:
wagon_length(lenght, wagon_lenght, p, n, k)
def wagon_length(lenght, wagon_lenght, p, n, k):
lenght = lenght - wagon_lenght[n]
wagon_lenght.remove(wagon_lenght[n])
k = k 1
if lenght > 0:
n = n-1
wagon_length(lenght, wagon_lenght, p, k, n)
elif lenght <= 0:
n = n-k
wagon_mass(weight, wagon_weight, p, k, n)
def wagon_mass(weight, wagon_weight, p, k, n):
res = sum(wagon_weight[-k:])
weight = weight - res
p = p - k
wagon_weight.remove(wagon_weight[p])
k = 0
if weight < 0:
print(p)
if weight >= 0:
bridge(p, k, n)
a = input()
lines = []
while True:
line = input()
if line:
lines.append(line)
else:
break
text = '\n'.join(lines)
bbh = [int(t) for t in text.split()]
arr = [int(d) for d in a.split()]
k = 0
weight = arr[1]
lenght = arr[0]
wagon_weight = bbh[1::2]
wagon_lenght = bbh[0::2]
n = len(wagon_lenght)-1
p = len(wagon_weight)-1
bridge(p, k, n)
我試著讓每次有一輛貨車撞到橋上時，我們在數字k上加一，這意味著當前在橋上的貨車數量，然后只需計算這個數量的貨車的總重量并減去它們從最大值開始——如果重量大于或等于零，那么這些貨車已經通過了。
But the mistake of my code is that when operations are performed with list, instead of the last wagons (I go from the last to the first), it deletes the smallest values ??and the code does not work as I intended
uj5u.com熱心網友回復：
我還沒有證明我的解決方案。可能有一些冗余代碼。
我的代碼將回傳第一個貨車的索引（基于 0 的索引），如果您希望最后一個只更新遞回，這將導致問題：
- 如果橋沒有被破壞，我的代碼將回傳 -1。
- 我的代碼將回傳(index,'s')意味著開始時的部分貨車將導致破壞
- 我的代碼將回傳(index,'e')意味著最后的部分貨車將導致破壞
- 我的代碼將回傳(index,'f')意味著開始時的完整貨車將導致破壞
我的代碼：
"""
- either wagon is fully on the bridge
- or partially placed on the bridge
- if partially place on the bridge:
* wagon is at starting point
* wagon is at last point
"""
import sys
sys.setrecursionlimit(10**8)
def move(wagonList, n , wagon , maxL, i, counter):
weight = wagon[1]
for j in range(i, n if counter > 0 else -1, counter):
if((maxL - wagonList[j][0]) <= 0):
weight = wagonList[j][1]
break
maxL -= wagonList[j][0]
weight = wagonList[j][1]
return weight
def moveCombo(wagonList, n , w , maxL, i,j):
if(i < 0 or j >= n or maxL <= 0):
return w
#return max(moveCombo(wagonList, n , w wagonList[j][1] , maxL-wagonList[j][0], i,j 1),moveCombo(wagonList, n , w wagonList[i][1] , maxL-wagonList[i][0], i-1,j))
return max(moveCombo(wagonList, n , w wagonList[j][1] , maxL-wagonList[j][0], i,j 1),
max(moveCombo(wagonList, n , w wagonList[i][1] , maxL-wagonList[i][0], i-1,j),
moveCombo(wagonList, n , w wagonList[j][1] wagonList[i][1] , maxL-wagonList[j][0]-wagonList[i][0], i-1,j 1)
))
def Gwagon(wagonList, n , maxL, maxW):
res = []
for i in range(n):
wagon = wagonList[i]
end = move(wagonList, n, wagon, maxL, i-1, -1)
start = move(wagonList, n, wagon, maxL, i 1, 1)
full = moveCombo(wagonList, n , wagon[1] , maxL-wagon[0], i-1, i 1)
if(start > maxW):
res.append((i,'s'))
if(end > maxW):
res.append((i,'e'))
if(full > maxW):
res.append((i,'f'))
if(res):
break
return res
def result(wagonList,n,maxL,maxW):
res = Gwagon(wagonList,n,maxL,maxW)
if(res):
print(*res)
else:
print(-1)
wagonList=[(10,90),(10,10),(9,80),(1,10),(9,10),(9,80),(5,10),(5,10),(1,10),(1,10),(1,10),(1,10),(1,40)]
result(wagonList,13,10,100)
wagonList=[(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
result(wagonList,7,7,20)
我的輸出：
-1
(0, 's')
- 我們的情況 1 橋梁不會被摧毀，所以 -1。
- 我們的案例 2 橋梁將被摧毀，第一輛貨車將是貨車編號 1 {4,5,5,7}。wagon -1 將作為起點，如果 wagon 部分在橋上，橋將被破壞。
新代碼：
"""
- either wagon is fully on the bridge
- or partially placed on the bridge
- if partially place on the bridge:
* wagon is at starting point
* wagon is at last point
"""
import sys
sys.setrecursionlimit(10**8)
def move(wagonList, n , wagon , maxL, i, counter):
weight = wagon[1]
obj = (weight,i-counter)
for j in range(i, n if counter > 0 else -1, counter):
if((maxL - wagonList[j][0]) <= 0):
weight = wagonList[j][1]
obj = (weight, j)
break
maxL -= wagonList[j][0]
weight = wagonList[j][1]
return obj
def moveCombo(wagonList, n , w , maxL, i,j, maxW):
if(i < 0 or j >= n or maxL <= 0 or maxW < w):
return (w,j-1)
o1 = moveCombo(wagonList, n , w wagonList[j][1] , maxL-wagonList[j][0], i,j 1, maxW)
o2 = moveCombo(wagonList, n , w wagonList[i][1] , maxL-wagonList[i][0], i-1,j ,maxW)
o3 = moveCombo(wagonList, n , w wagonList[j][1] wagonList[i][1] , maxL-wagonList[j][0]-wagonList[i][0], i-1,j 1, maxW)
res = (0,n 1)
if(o1[0] > maxW):
res = o1
if(o2[0] > maxW):
if(res[1] > o2[1]):
res = o2
if(o3[0] > maxW):
if(res[1] > o3[1]):
res = o3
return res
def Gwagon(wagonList, n , maxL, maxW):
res = []
for i in range(n):
wagon = wagonList[i]
end = move(wagonList, n, wagon, maxL, i-1, -1)
start = move(wagonList, n, wagon, maxL, i 1, 1)
full = moveCombo(wagonList, n , wagon[1] , maxL-wagon[0], i-1, i 1, maxW)
if(start[0] > maxW):
res.append((start[1],'s'))
if(end[0] > maxW):
res.append((end[1],'e'))
if(full[0] > maxW):
res.append((full[1],'f'))
if(res):
break
return res
def result(wagonList,n,maxL,maxW):
res = Gwagon(wagonList,n,maxL,maxW)
if(res):
res.sort()
print(res[0][0] 1)
else:
print(-1)
wagonList=[(10,90),(10,10),(9,80),(1,10),(9,10),(9,80),(5,10),(5,10),(1,10),(1,10),(1,10),(1,10),(1,40)]
result(wagonList,13,10,100)
wagonList=[(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
result(wagonList,7,7,20)
輸出：
-1
4
uj5u.com熱心網友回復：
您可以將貨車的序列轉換為火車每米長度的增加和減少重量的序列。這兩個序列將被橋的長度抵消，這樣您就可以將它們加在一起，并在火車每次移動一米時獲得橋上的總負載。itertools 的累積函式可以幫助計算每米的總負載：
from itertools import accumulate
def support(bridge,capacity,wagons):
index = [i for i,(wl,_) in enumerate(wagons,1) for _ in range(wl)]
start = accumulate(w for wl,ww in wagons
for w in [ww] [0]*(wl-1))
end = accumulate(-w for wl,ww in [(bridge,0)] wagons
for w in [0]*(wl-1) [ww])
load = map(sum,zip(start,end))
return next((index[m] for m,w in enumerate(load) if w>capacity),-1)
輸出：
bridge = 10
capacity = 100
wagons = [(10,90),(10,10),(9,80),(1,10),(9,10),(9,80),(5,10),(5,10),
(1,10),(1,10),(1,10),(1,10),(1,40)]
print(support(bridge,capacity,wagons)) # -1
bridge = 7
capacity = 20
wagons = [(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
print(support(bridge,capacity,wagons)) # 6
bridge = 5
capacity = 10
wagons = [(5,5),(5,5),(5,5),(5,5),(5,5),(5,100),(5,100),(5,100)]
print(support(bridge,capacity,wagons)) # 6
例如：
bridge = 7
capacity = 20
wagons = [(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
index將包含在相應儀表位置添加到橋上的貨車的 idstart是添加到橋上的貨車的貨車重量的累積總和end是離開橋梁的貨車的貨車重量的累積總和（負）load是當列車相應的儀表到達橋時橋上的實際負載（增加 - 離開）。- 在橋上添加最后一輛貨車后，無需進一步檢查容量，因為此后負載只會減少
...
index 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7
enter 4 0 0 5 0 0 5 0 0 7 0 0 7 0 0 7 0 0 6 0 0
(leaving) 1 1 1 2 2 2 3 3 3 4 4 4 ...
leave 0 0 0 0 0 0 0 0 0 -4 0 0 -5 0 0 -5 0 0 -7 0 0 ...
start 4 4 4 9 9 9 14 14 14 21 21 21 28 28 28 35 35 35 41 41 41
end 0 0 0 0 0 0 0 0 0 -4 -4 -4 -9 -9 -9 -14 -14 -14 -21 -21 -21 ...
load 4 4 4 9 9 9 14 14 14 17 17 17 19 19 19 21 21 21 20 20 20
^
Overload here _______|
沒有庫 （相同的邏輯）
def support(bridge,capacity,wagons):
index = (i for i,(wl,_) in enumerate(wagons,1) for _ in range(wl))
enter = (w for wl,ww in wagons for w in [ww] [0]*(wl-1))
leave = (w for wl,ww in [(bridge,0)] wagons for w in [0]*(wl-1) [ww])
load = 0 # current load on bridge
for i,more,less in zip(index,enter,leave): # examine each meter
load = more-less # track total weigth
if load>capacity: return i # detect overload
return -1
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/392873.html