之前一直都丟在luogu，現在終于放這了

n個東西需要加工，在A加工的時間是ai, 在B加工的時間是bi,每個東西必須在A加工完后才能在B加工，求最少時間

貪心大體思路：不要讓A有空閑時間，B的空閑時間盡量少是最優的

對于貪心思路采用歸納法

對于n = 1的情況，顯然最少時間是a1 + b1

---

對于n = 2的情況：

第一種情況：

假設生產順序是先(a1, b1)再(a2, b2)：

如果b2加工前最后是在等待a2，也就是b1<a2，所以Tmin = a1 + a2 + b2

如果b2加工前最后是在等b1,也就是b1>a2，那么Tmin = a1 + b1 + b2

則容易看出Tmin = a1 + b1 + a2 + b2 - min(b1, a2)

第二種情況：

假設生產順序是(a2,b2)再(a1,b1)，同理可得Tmin = a1 + b1 + a2 + b2 - min(b2, a1)

綜上，Tmin = a1 + b1 + a2 + b2 - max(min(b1, a2), min(b2, a1))

則可以得到Johnson不等式：

對于兩個待加工的東西x, y，排序

min(x1, y2) < min(x2, y1)

會使得最終答案最優

其實就是，對于所有待加工的東西所花時間(a, b)分成p1類別a <= b和p2類別a > b，對于p1按a遞增排序，對于p2按b遞減排序，先執行第一種，再執行p2種，得到的答案一定最優

Johnson不等式和這個貪心思路為什么得到的順序一定相同呢？

對于(a1, b1)和(a2, b2)，假設a1 <= b1屬于p1類別，a2 > b2屬于第二類別

因為Johnson不等式有min(a1, b2) < min(a2, b1)，無論左邊的是a1小還是b2小，都一定小于右邊的min(a2, b1)，所以能夠得到上面的思路

---

總結

以上是生活随笔為你收集整理的可能是流水调度问题的证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。