輸入說明
我輸入的第一行包含兩個數字：?? 和 ??，分別表示集裝箱(2 ≤ ?? ≤ 20,000)數量和交貨數量（不超過100,000）
在下面的 ?? 行中有成對的數字：?? 和 ??，其中 ?? 是交付的貨車數量（不超過20,000），?? 是每輛貨車中的礫石數量（不超過20,000）。
所有交貨的貨車總數不超過1,000,000.
在任何輸入容器中都不會包含超過1,000,000,000礫石的情況。
問題陳述
貨車一次清空一個，均勻地放入兩個連續的容器中。這些是確定選擇哪兩個相鄰容器的規則（其中containers[]表示n當前容器大小的串列）：
- 在所有與 的對
(containers[i], containers[i 1])中0 <= i < n - 1，選擇最小化的對min(containers[i], containers[i 1]) - 如果有平局，則在平局對中選擇最小化的對
max(containers[i], containers[i 1])（即最小化對中第二小的元素） - 如果仍有平局，則在平局對中選擇
(containers[i], containers[i 1])索引最小i的對。
礫石均勻地分布在這對中。如果貨車中的礫石數量為奇數，則 ID 較小的容器獲得剩余（1 個卵石）。
起初，所有容器都是空的。
例如：
lista = [0, 4, 3, 2, 0, 5, 4, 0, 3, 4, 2, 0]
My first smallest value in that list is 0 so there are 6 possibilities for different pairs
0,4 with indices 0 and 1
0,2 with indices 3 and 4
0,5 with indices 4 and 5
4,0 with indices 6 and 7
2,0 with indices 10 and 11
My second smallest value in this 6 possibilities is 2 so I have two options
0,2 with indices 3 and 4
2,0 with indices 10 and 11
Indexes 3 and 4 are less than 10 and 11 so we will be dropping the wagons into containers with indexes [3, 4]
In the output:
Each of the ?? lines of output data should contain a single number - the number of pebbles
in a container. The order of listing should be the same as the order of the identifiers.
Example
For the example input shown below:
6 4
4 3
1 2
2 14
4 3
the correct answer is:
6
10
12
7
11
8
Explanation of the example
In the first delivery:
- The first wagon can be unloaded into pairs of containers
(1, 2), (2, 3), (3, 4), (4, 5), (5, 6).
We choose the first one and the values ??of the filling are(2 1 0 0 0 0). - Second wagon can be put into pairs of containers
(3, 4), (4, 5), (5, 6).
We choose the first one and the filling values ??are(2 1 2 1 0 0). - The third wagon can be put into a pair of containers
(5, 6), which will give us the values ??of the fills
(2 1 2 1 2 1). - The fourth wagon may be discharged into par
containers
(1, 2), (2, 3), (3, 4), (4, 5), (5, 6). We choose the first one and the filling values is(4 2 2 1 2 1).
- The first wagon can be unloaded into pairs of containers
The second delivery changes the capacity of the containers as follows:
(4 2 3 2 2 1).In the third delivery:
- The first wagon may be unloaded only into a pair of containers
(5, 6), and then the values ??for the fills are (4 2 3 2 9 8). - The second car can be unloaded into pairs
(2, 3)or(3, 4). We choose the first one and the fill values ??are(4 9 10 2 9 8).
- The first wagon may be unloaded only into a pair of containers
最后一次交貨更改填充物如下：
(4 9 10 4 10 8),(6 10 10 4 10 8),(6 10 12 5 10 8),(6 10 12 7 11 8)
下面是我的程式代碼（它可以作業，但是，它不是大數字的最佳選擇）
n, d = map(int, input().split())
containers = []
for _ in range(n):
containers.append(0)
for _ in range(d):
wagons, gravel = map(int, input().split()) # w, z
half_gravel = int(gravel/2)
greater_half = int(gravel/2) gravel%2
for _ in range(wagons):
i = min(range(len(containers) - 1),
key=lambda i: sorted(containers[i : i 2]))
containers[i] = greater_half
containers[i 1] = half_gravel
for i in containers:
print(i)
提前感謝您在優化程式方面的幫助
uj5u.com熱心網友回復：
您可以通過使用最小堆（即優先級佇列）更有效地解決這個問題，例如Python 標準庫中提供的那個。堆的主要目的是有效地跟蹤集合的最小元素，洗掉該最小值并添加新元素，這準確地反映了您的問題。
目前，該行：
i = min(range(len(containers) - 1),
key=lambda i: sorted(containers[i : i 2]))
在你最里面的回圈中是一個O(n)成本操作，每次遍歷所有容器。您可以O(log n)通過保留 3 元組的最小堆來提高成本，這相當于：
min_heap = (min(containers[i:i 2]), max(containers[i:i 2]), i)
for i in range(n-1)
這些 3 元組中的最小值，使用標準的字典順序，給出下一個容器來接收礫石。重要的是，我們不需要在回圈中實際重建這個堆，只需更新它
這里有一個微妙之處：一個容器一次可以是這兩個 3 元組的成員，所以如果我們更新一個容器對并將其 3 元組推回堆上，就會有一個過期的 3 - 最小堆中的元組，其值小于應有的值。這很好：我們可以實作一個減少鍵函式（使用這個堆相當困難），或者，只使用延遲更新。
對于“延遲更新”，當從堆中彈出時，我們檢查堆的“報告的最小值”是否已過期，將其洗掉，然后重新插入更新版本。使用攤銷分析，因為會發生這種額外的堆操作成本每輛貨車最多累積一次，該演算法的運行時間仍然是
O(n total_wagons * log(n)).
Python代碼：
n, d = map(int, input().split())
containers = [0]*n
# Heap elements will be: (min(pair), max(pair), i) for pair = container[i:i 2]
min_heap = [(0, 0, i) for i in range(n-1)]
for _ in range(d):
wagons, gravel = map(int, input().split()) # w, z
half_gravel = gravel // 2
greater_half = (gravel // 2) gravel % 2
for _ in range(wagons):
# Find minimum element
while True:
smaller, larger, index = heapq.heappop(min_heap)
# Check if entry is out of date
actual_pair = sorted([containers[index], containers[index 1]])
if actual_pair != [smaller, larger]:
heapq.heappush(min_heap, (actual_pair[0], actual_pair[1], index))
else:
break
containers[index] = greater_half
containers[index 1] = half_gravel
new_smaller, new_larger = sorted([containers[index], containers[index 1]])
# This may cause index 1 entry to be out of date, which is OK.
heapq.heappush(min_heap, (new_smaller, new_larger, index))
for i in containers:
print(i)
注意：這種惰性更新策略通常用于避免需要減少鍵，并且在 Dijstra 演算法中更常用。但是，僅當佇列中的元素的存盤值可能小于其真實值時，它才有效，反之則不行。
The while True: loop looks a bit strange, but it's used because there may be up (in theory) O(n) out-of-date elements in the heap, so we need to keep popping, checking, and updating if the reported minimum is out-of-date.
How can we tell the number of elements in the heap doesn't change between wagons? At the start of every iteration of that loop, there has been no net change in the number of elements. In each iteration, we perform a pop at the start. Then, either we:
- Find an out-of-date element, perform a push and continue (net 0),
- Break (net -1 elements).
So after the while True loop, we are always at net -1 elements. After the loop, we always perform a push, bringing us back to no net change in heap size.
uj5u.com熱心網友回復：
我贊同@kcsquared 的方法，但會發布一個在所有方面都不那么“聰明”的變體，因此更可能是顯而易見的 ;-) 輸出與您在給出的單個測驗用例中的期望相匹配。
編輯：正如評論中指出的那樣，這并不總能解決上述問題。不過，我將把答案放在這里，因為它在其他方面具有指導意義。
from heapq import heapreplace
containers = [0] * n
h = [(0, i) for i in range(n)]
for wagons, gravel in [(4, 3),
(1, 2),
(2, 14),
(4, 3),
]:
half_gravel = gravel // 2
greater_half = gravel - half_gravel
for _ in range(wagons):
while True:
val, i = h[0]
if val != containers[i]:
heapreplace(h, (containers[i], i))
else:
break
if i == len(containers) - 1:
i -= 1
elif i and containers[i-1] <= containers[i 1]:
i -= 1
containers[i] = greater_half
containers[i 1] = half_gravel
for i in containers:
print(i)
assert containers == [6, 10, 12, 7, 11, 8]
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/438323.html