**Chapter 4 II**
### 貪心搭配二分搜
貪心演算法經常可以搭配二分搜，以下舉兩個例子。
---
##### P-4-9. 基地台 (APCS201703)
直線上有 $N$ 個要服務的點，每架設一座基地台可以涵蓋直徑 $R$ 範圍以內的服務點。輸入服務點的座標位置以及一個正整數 $K$，請問：在架設 $K$ 座基地台以及每個基地台的直徑皆相同的條件下，基地台最小直徑 $R$ 為多少？
Time limit: 1秒
輸入格式：輸入有兩行。第一行是兩個正整數 $N$ 與 $K$，以一個空白間格。第二行 $N$ 個非負整數 $P[0],P[1],\ldots ,P[N-1]$ 表示服務點的點座標，相鄰數字以空白間隔。座標範圍不超過1e9，$1\le K < N \le 5e4$。
輸出：最小的基地台直徑。
範例輸入：
6 2
5 2 1 7 5 8
範例結果：
3
---
服務點可以看成數線上的點，基地台可以看成數線上的線段，要計算以 $K$ 根長度相同的線段蓋住所有的點，所需最小的線段長度。
這一題是給數量 $K$ 要求長度 $R$。要解決這個問題，先看以下問題：輸入給數線上 $N$ 個點以及 $R$，請問最少要用幾根長度 $R$ 的線段才能蓋住所有輸入點。
我們以貪心法則來思考。考慮座標值最小的點 $P$，如果有一個解的最左端點小於 $P$，我們可以將此線段右移到左端點對齊 $P$，這樣的移動不會影響解的合法性，因此，可以得到以下結論：「一定有一個最佳解(最少的 $K$)是將一根線段的左端放在最小座標點上。」因此，我們可以放上一個線段在 $[P,P+R]$，然略過所有以被蓋住的點，對剩下的點繼續此步驟。重複執行到所有的點被蓋住，就可以找到最小的 $K$ 值。
回到我們的原來問題。假設$f(R)$是給定長度 $R$ 的最少線段數，那麼上述的演算法可以求得 $f(R)$。很直覺地，當 $R$ 增加時，$f(R)$ 必然只會相同或減少，因為用更長的線段去蓋相同的點，不會需要更多線段。所以我們可以二分搜來找出最小的 $R$，滿足 $f(R)\le K$。
以下是範例程式。先寫一個函數 $enough(r)$ 計算長度 $r$ 的線段是否足夠，我們不需要算出最少的線段數量，只要知道 $K$ 根是否足夠即可。主程式中將點座標排序後，就以二分搜來找出**最長的不足夠**長度，最後加一就是最短的足夠長度。這裡的二分搜採取第二章介紹的一路往前跳的方式。
時間複雜度是$O(n\log R)$，其中 $R$ 是座標範圍。
```python=
n, k = map(int, input().split())
p = [int(x) for x in input().split()]
p.sort()
# if length r is enough to cover all points by k segment
def enough(r):
last = -1 # last covered
seg = k # remaining segment
for pi in p:
if pi > last:
if seg == 0: return False
seg -= 1 # use a new segment
last = pi+r
return True
#
# binary search to find largest not-enough
r = 0
jump = (p[-1]-p[0])//2 # range size//2
while jump:
while not enough(r+jump):
r += jump
jump >>= 1
#
print(r+1)
```
下一題是類似的習題。
---
##### Q-4-10. 恢復能量的白雲熊膽丸
令狐沖闖黑木崖要依序通過 $n$ 個關卡，第 $i$ 個關卡要消耗 $p[i]$ 的能量，如果能量不足就會闖關失敗。不管當時的能量剩下多少，吃下一顆恆山派的「白雲熊膽丸」就會讓令狐沖的能量值恢復到滿額的 $F$。假設在開始時能量是$F$，闖關過程中最多只能服用 $m$ 次，輸入 $p[]$ 與 $m$，請問令狐沖的能量額 $F$ 至少必須是多少才能闖關成功。請注意，連吃兩顆是沒用的，能量還是 $F$。
Time limit: 2秒
輸入格式：第一行是正整數 $n$ 與非負整數 $m$，第二行，有 $n$ 個正整數$p[1], p[2],…,p[n]$。$p[i]$不超過1e5，$0 \le m < n \le 1e5$。
輸出：輸出 $F$ 的最小值。
範例輸入：
7 2
3 4 1 7 4 1 2
範例結果：
8
說明:闖過三關 (3,4,1)，吃藥，闖過 (7)，再吃藥，闖過最後3關 (4,1,2)。$F=7$ 的話至少要吃三次藥才能通過。
---
### 掃描線演算法sweep-line
掃描線演算法的名字來自在解某些幾何問題時，想像用一條掃描線沿著某個方向掃描，過程中記錄某些資料或維護某些結構。因此與貪心演算法類似，往往第一步就是排序。常見的題目有數線上的點或線段，以及平面上的點或直線。限於難度，這裡僅提出一些經典而不太複雜的題目。
---
##### P-4-11. 線段聯集 (APCS 201603)
輸入數線上的 $N$ 個線段，計算線段聯集的總長度。
Time limit: 2秒
輸入格式：第一行是一個正整數 $N$，接著的 $N$ 行每一行兩個非負整數，代表一根線段的左端點與右端點，左端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。$N$ 不超過1e5，座標絕對值皆不超過1e8
輸出：線段聯集總長度。
範例輸入：
5
10 20
20 20
30 75
5 15
40 80
範例結果：
65
---
這一題有個比較簡單的常見版本是座標範圍很小而且線段數量也不多，例如 $N$ 是1000而座標範圍在 0 ~ 1000。在此情形下把 $[0,1000]$ 這個區間看成1000個長度為1的區段，以一個陣列$seg[]$ 來記錄每一個區段是否有被線段覆蓋。具體來說：
$seg[i] = 1$ if 區間 $[i,i+1]$ 有被覆蓋，否則 $seg[i] = 0$。
初始時，所有 $seg[i] = 0$，表示沒有線段。對於每一個輸入的線段 $[left, right]$，我們將陣列 $seg[left:right]$ 的區段都設為1，模擬將線覆蓋在區間上。等到所有線段都處理完畢後，數一數有多少區段被設為1就知道覆蓋的總長度了。
以下是範例程式，可以通過測資中的前三筆。留意到第6行list的slicing可以放在等號左邊去更改其中一段。
```python=
# P-4-11, subtask, table method O(total length)
n = int(input())
seg = [0]*1001
for i in range(n):
left,right = [int(x) for x in input().split()]
seg[left:right] = [1]*(right-left)
print(sum(seg))
```
這個方法的複雜度是線段長度的總和，在大座標範圍時的效率很差。若要與座標範圍無關，基本想法是將線段逐一加入，維護好目前的聯集 $S$，$S$ 顯然是一群不相連的線段。每次加入一根線段時，如果他與 $S$ 中的線段沒有交集，那太好了，把他放進去就行了；如果有交集呢？就必須將有交集的部分找出來做成聯集。這樣做不是不行，但是非常的麻煩。我們試試看掃描線的想法。
想像有根掃描線，從左往右掃，過程中我們一樣保持住目前已經看到的線段的聯集 $S$。掃描過程可能碰某個線段的左端或是右端，其他的位置對線段聯集的變化並無影響可以忽略。碰到某線段左端時，代表有一個線段要加入 $S$。從左往右掃的好處是，當一個線段 $[x,y]$ 加入時，最多只會跟 $S$ 中的一根線段(最後一根)有交集！因為他的左端 $x$ 不會在 $S$ 中任何一根線段的左方(記得吧，我們從左往右)。什麼時候沒交集呢？如果 $x$ 大於S中的最大右端。而且，如果這個線段與 $S$ 沒交集，後面的線段也都不會再跟 $S$ 有交集，因為後面的線段的左端都大於等於 $x$。
這麼一來，程式就很好寫了，我們只要依照線段左端從小到大的順序逐一將線段加入 $S$，維護好 $S$ 中的最後一根線段就好了。以下是範例程式，我們用$last$維護目前聯集中的最後一段，將輸入線段依照左端排序後一一加入，時間複雜度$O(n\log n)$，因為排序。
```python=
# P4-11 union of segments, sweeping O(nlogn)
n = int(input())
seg = []
for i in range(n):
seg.append([int(x) for x in input().split()])
seg.sort() # sort by left
total = 0 # total length
last = [-1,-1] # last segment, initial
for left,right in seg:
if left > last[1]: # disjoint
total += last[1] - last[0]
last = [left,right]
else: # merge last and s[i]
last[1] = max(last[1], right)
#
total += last[1] - last[0] #// don't forget
print(total)
```
這一題有另外一個想法來做，我們如果去觀察每個點經過的線段數量(稱為厚度)，$n$根線段會將數線分成若干區間，每一區間的厚度與前後不同，但區間數最多不超過$2n+1$。我們可以把這些區間全部求出來，厚度大於0的就是我們這一題要的答案。
對於一個線段$[x,y]$，我們把他想成在$x$進入，在$y$離開，也就是如果掃描線由左往右，到達$x$時，厚度要加一，到達$y$時厚度要減一。我們把所有厚度要加減的位置放在一個陣列中，依照座標排序後，由左到右掃描即可。
以下是範例程式。這個方法其實是**差分**的概念，假設我們把每一點座標的厚度當成一個序列$t(i)$，則$d(i)=t(i)-t(i-1)$則是 $t$ 的差分，而且 $t$ 則是 $d$ 的prefix sum (初值設0)。差分與前綴和就是微分與積分的離散版本，微分與積分是對連續函數，差分與前綴和則是對離散函數(也就是序列)。
線段厚度的例子其實只是對於給定的差分，用前綴和求出所有不同厚度的區段而已。
```python=
# P4-11 union of segments, using difference O(nlogn)
n = int(input())
dif = []
for i in range(n):
left,right = [int(x) for x in input().split()]
dif.append([left,1])
dif.append([right,-1])
dif.sort() # sort by coordinate
total = 0 # total length
thick = 0 # current thickness
last = -1 # start of curr thick
for p,q in dif:
if thick > 0:
total += p-last # [last,p] has segment
last = p
thick += q # update
#
print(total)
```
下面一個例題非常簡單又直覺，但是很有趣的是，我們稍後會看到他的另外一種形式，當他以另外一個形式出現時，卻似乎比較難理解。
---
##### P-4-12. 一次買賣
某商品在某個時期每一天的價格是 $p(1), p(2),…,p(n)$。假設只能先買後賣，請計算買賣一次的最大獲利價差，允許當天買賣，也就是一次都不買(獲利0)。
Time limit: 1秒
輸入格式：第一行是正整數 $n$，第二行有 $n$ 個正整數$p(1), p(2),…,p(n)$。$n$ 不超過1e5，價格皆不超過1e9。
輸出：買賣一次的最大價差。
範例輸入：
5
3 5 1 4 0
範例結果：
3
---
範例中暗示你，挑選最大值與最小值的差並非正確的答案。我們只需要考慮在第 $i$ 天賣出的最大獲利，然後對各個 $i$ 取最大值就是答案了。第 $i$ 天賣出的最大獲利當然就是買在 $i$ 以前出現的最小值，也就是 $i-1$ 的prefix-minimum。所以我們可以一路掃描過去，維護好prefix-min，再取較大的價差就好了，以下是範例程式。
```python=
# P-4-12 max price difference, O(n)
n = int(input())
price = [int(x) for x in input().split()]
pmin = 1000000 # prefix min
maxd = 0 # max difference
for p in price:
maxd = max(maxd, p - pmin)
pmin = min(pmin, p)
#
print(maxd)
```
下面這一題是教學的經典名題，有人把他在貪心算法，也有人可能歸類到動態規劃。網路上找得到很多解法的介紹。
---
##### P-4-13. 最大連續子陣列
輸入一個整數陣列$A[1:n]$，請計算$A$的連續子陣列的最大可能總和，空陣列的和以0計算。
Time limit: 2秒
輸入格式：第一行是正整數 $n$，第二行有 $n$ 整數 $A[1], A[2], …, A[n]$。$n$ 不超過1e5，陣列內容絕對值不超過1e9。
輸出：最大可能總和。
```
範例一輸入：
8
4 12 -17 5 8 -2 7 -3
範例一輸出：
18
範例二輸入：
3
-1 -1 -1
範例二輸出：
0
```
---
P-4-13與P-4-12有何關係呢？P-4-12的輸入是每日價格，如果把每日價格與前一日的價差放在 $A[]$ 中，$A[i]=p(i)-p(i-1)$，那麼就變成P-4-13了，因為連續一段時間的累積價差就等於最後一日與最前一日的價差
$$
\begin{array}{ll}
&A[i]+A[i+1]+\ldots +A[j] \\
=&(p(i)-p(i-1))+(p(i+1)-p(i))+…+(p(j)-p(j-1))\\
=&p(j)-p(i-1)
\end{array}
$$
P-4-12的$O(n)$解法非常直覺明顯，而P-4-13的$O(n)$解法則似乎比較不容易。當然你可以把輸入轉換成前一題的輸入，但我們也可以直接看這個題目。
最簡單的解法是窮舉$O(n^2)$個所有區間(子陣列)，每一個區間再用一個迴圈求和，這樣導致了一個$O(n^3)$的解。改善複雜度降到$O(n^2)$有兩個方法，一種是對所有左端 $i$，用一個迴圈求出所有$[i,j]$區間的最大和，這個很容易做到因為
$sum(A[i:j+1]) = sum(A[i:j])+A[j]$。
另外一種方法是利用前綴和(prefix sum)。先算好前綴和之後，每一個區間和可以用一個減法完成。
但是這兩種都不夠好，從前一題就知道這題可以在$O(n)$求解。令$f(i)$是以 $i$ 為右端(各種可能的左端)的最大區間和。觀察$f(i+1)$與$f(i)$的關係，$f(i+1)$所選的左端如果在$i$之前，那麼一定與$f(i)$的左端一樣。所以$f(i+1)$只有以下兩種可能：
* $f(i+1)=f(i)+A[i+1]$，左端與$f(i)$相同；或者
* $f(i+1)=A[i+1]$，左端在$i+1$。
兩者挑大的就好了，事實上，這就像一代一代累積財產，若$f(i)>0$，爸媽留給你的是正資產，則繼承過來；否則就拋棄繼承。這樣一比喻，這題的解其實也是非常直覺自然的。以下是範例程式。
```python=
# P-4-13 max subarray, O(n)
n = int(input())
a = [int(x) for x in input().split()]
pmax = 0 # max sum ended at previous i-1
max_sum = 0 # max sum of subarray
for p in a:
pmax = max(pmax,0) + p
max_sum = max(max_sum, pmax)
#
print(max_sum)
```
下兩題是平面幾何的題目，兩題都常被拿來當作分治演算法(下一章的主題)的教材，但事實上都有掃描線的解法。
---
##### P-4-14. 控制點(2D-max)
平面上有N個點，第 $i$ 點的座標為$(x[i], y[i])$。若 $x[i] \le x[j]$ 且 $y[i] \le y[j]$，則我們說第 $j$ 點可以控制第 $i$ 點。我們希望能在輸入的點中，選取最少的點做為控制點，使得每一個輸入的點都至少被一個控制點所控制。輸入N個點的座標，請計算出最少要選取多少個控制點。以下圖為例，輸入8個點中，右上方圈起的四個點即是最少選取的控制點。
Time limit: 1秒
輸入格式：每筆測試資料的第一行為一個正整數$N$，$N\le 1e5$。第二行有 $N$ 個非負整數，依序是這些點的X座標，第三行有 $N$ 個非負整數，依序是這些點的Y座標，座標值不超過1e9。
輸出：輸出最少的控制點數量。
範例一：輸入
4
1 2 3 3
1 2 3 3
範例一：正確輸出
1
範例二：輸入
8
3 1 5 3 4 7 8 9
8 2 5 1 2 4 2 3
範例二：正確輸出
4
---
這個題目稱為2D Maximal point，2D平面上的maximal point是指沒有人的XY皆大於等於此點，是否會有相同座標點輸入則看題目定義，本題是允許，但本題中如果有兩個相同座標的極大點，只需要選一個。
直接的做法可以兩兩比對，複雜度$O(n^2)$，無疑是不夠好。假設我們從左到右掃描這些點，維護好目前找到的解(maximal points)，假設做到第 $i-1$ 點時的解是$S(i-1)$，考慮當第 $i$ 點$(x[i],y[i])$進入時的狀況。
$S(i-1)$中Y值不大於$y[i]$的點都應該從解中移除，因為前面點的X值都不大於$x[i]$；而$(x[i],y[i])$必然是$S(i)$中的點，因為他具有目前最大的X值。要如何刪除$S(i-1)$中Y值不大於$y[i]$的點呢？乍看之下以為要使用什麼特別的資料結構，但其實並不需要。因為maximal的點是以X值遞增的方式加入，他們的Y值一定是遞減，只要從後往前刪除就可以了。從後往前刪除，然後自己加入到最後面，所以Stack是好的選擇，如果有印象的話，這個方法在前一章找前方的高人那個題目中使用過。
請看以下範例程式，先將X與Y座標讀入後，以 zip(px,py) 將兩個list一一對應的數對建構出點座標的list point，此時，point的每一個元素是一個(x,y)的tuple。接著，我們將point排序，根據lexicographic order，X比較小的會在前面，相同X值時，Y值小的在前面，這剛好符合我們的需要。
接著，我們準備一個stack，這個是用來放Y的遞減序列，初始時放一個oo是當作哨兵，省略stack是否為空的檢查。
除了排序外的時間複雜度是$O(n)$，因為每個點最多進出stack一次。
```python=
# P-4-14 2d max subarray, stack, O(nlogn)
n = int(input())
px = [int(x) for x in input().split()]
py = [int(x) for x in input().split()]
point = list(zip(px,py))
point.sort() # smaller x, if x1=x2 then smaller y
stk = [10**9+1] # decreasing y-value of current maximal
# a sentinel oo
for x,y in point: # x from small to large
while y >= stk[-1]:
stk.pop(); # delete smaller y
stk.append(y)
#
print(len(stk)-1) # excluding sentinel
```
事實上這個題目有更簡單的寫法。當我們從左往右掃描時，前面找到的maximal point有可能需要刪除，如果從右往左掃描呢？因為看到的點的X值是遞減，先找到的maximal point就一定是在解中的點！我們只要記住目前右方的最大Y值就可以決定下一點是否需要加入解中了(如果他有更大的Y值)。以下是範例程式，除了排序外，時間複雜度顯然是$O(n)$，與前面那支一樣。
```python=
# P-4-14 2d max subarray, backward, O(nlogn)
n = int(input())
px = [int(x) for x in input().split()]
py = [int(x) for x in input().split()]
point = list(zip(px,py))
point.sort() # smaller x, if x1=x2 then smaller y
max_y = -1 # currently max y
total = 0 # number of maximal points
for x,y in point[::-1]: # backward
if y > max_y:
total += 1 # a new maximal point
max_y = y # uupdate
#
print(total)
```
下一題也是平面上的點的問題，有點難，需要一點幾何特性。
---
##### P-4-15. 最靠近的一對(closest pair) (@@)(\*)
平面兩點的$L_1$距離為兩點的X差值與Y差值的和，也就說，如果兩點座標是$(a,b)$與$(c,d)$，則$L_1$距離是$|a-c|+|b-d|$。輸入 $n$ 個點的座標，請計算出$L_1$距離最近兩點的$L_1$距離。
Time limit: 4秒
輸入格式：第一行為一個正整數 $n$，接下來 $n$ 行，每行兩個整數 $x$ 與 $y$ 代表一點的座標。$n$ 不超過1e5，座標值絕對值不超過1e9。
輸出：最近兩點的$L_1$距離。
範例輸入：
4
-1 5
4 0
3 1
-2 -3
範例結果：
2
---
這個題目也是演算法的經典題，但是在這裡出現時，需要用到一個特殊的資料結構，所以是超過APCS範圍的解法。我們在下一章分治演算法也會再談到它，從分治的角度，這題並不算超過APCS的範圍。網路上可以找到這題的很多相關資料與教學，大部分是直線距離的版本，也就是兩點之間的距離以直線距離計算，在線性代數中，直線距離稱為$L_2$，與這一題的$L_1$距離雖然不一樣，但是類似，$L_1$距離也有很多重要的應用，例如在IC設計上，網路上有很多說明資料。這一題用$L_1$只是為了計算更簡單而且不需要浮點數，演算法其實是一樣的。
想像一根垂直掃描線由右往左掃過去，計算出目前的解，也就是目前已經納入點的最小距離，每次碰到一個新的點，就找出新點與前面點的最近距離，並更新最小距離。如果有多點X值若相同，以任意順序並無影響。假設每個新進點都要跟前面的點計算距離，那這個方法跟窮舉沒兩樣，所以我們要想辦法減少計算的點數。
假設目前碰到的點是$p[i]=(x[i]，y[i])$而目前已求出來的最小距離是$d$，令$S$是 $p[0]$ ~ $p[i-1]$這些點的集合(如果沒有相同X可以簡單說 $p[i]$ 左方的點)，也就是說$S$中任兩點的距離至少是 $d$。
首先，$S$ 中只有Y座標值在 $[y[i]-d, y[i]+d]$ 範圍內的點才需要計算，因為其他的點到 $p[i]$ 的距離必然大於 $d$；此外，根據相同的理由，$S$中X座標值小於 $x[i]-d$ 的點都不需要計算，而且不止這回合，以後碰到新點時，這些太左邊的點也都不需要計算了，因為越後面的點X座標越大。根據這兩個觀察，我們可以來寫程式了。
為了有效地找到Y座標在 $[y[i]-d, y[i]+d]$ 範圍內的點，因為需要增加與刪除資料，我們需要一個動態資料結構可以很快找到一個範圍。Python並無內建這樣的資料結構，假設我們以list搭配bisect來做，它跑得還算快，但worst case仍是$O(n^2)$，以下是這樣的程式。
```python=
# P_4_15 closest pair, sweep line, L1 distance
# using bisect_left + insort + list.pop
import bisect
n = int(input())
point = [] # [x,y]
for i in range(n):
point.append([int(x) for x in input().split()])
point.sort() # sort by x
py = [] # previous (y,x), sort by y
min_d = 2000000001 # min distance
for x,y in point: # for each point from left to right
# check [p.y-d, p.y+d]
out = [] # out of range, to be del
i = bisect.bisect_left(py, (y - min_d,0))
while i < len(py) and py[i][0] < y+min_d:
if py[i][1] <= x - min_d: # out of date, remove
out.append(i)
else: # check if better
min_d = min(min_d, abs(x-py[i][1])+abs(y-py[i][0]))
i += 1
#
for q in out[::-1]: py.pop(q)
bisect.insort(py, (y,x)) # insert, sorted
#
print(min_d)
```
為了要動態的維護排好序的資料，Python有個SortedList可以使用，但不在標準函數庫內，他的新增刪除查詢均為$O(\log n)$的時間。以下是範例程式，這個程式跟前一支很像，只是用了不同得資料結構。第2行是引入此資料結構，第8行是初始化SortedList，我們將在其中擺$(y,x)$的tuple，它會始終保持排好序的狀態。第10行開始依照X由小到大歷遍所有的點，第13行找出在Y座標在範圍內的點，如果他的X座標已經太小，我們將它放入out中準備刪除(第15行)；否則計算距離看看是否找到更小的距離(第17行)。在這個點搜尋完畢後，我們刪除那些要刪除的點(第19行)，然後將此點加入(第20行)。
```python=
# P_4_15 closest pair, sweep line, L1 distance
from sortedcontainers import SortedList
n = int(input())
point = [] # [x,y]
for i in range(n):
point.append([int(x) for x in input().split()])
point.sort() # sort by x
py = SortedList() # (y,x), sort by y
min_d = 2000000001 # min distance
for x,y in point: # for each point from left to right
# check [p.y-d, p.y+d]
out = [] # out of range, to be del
for qy,qx in py.irange((y - min_d,0), (y+min_d+1,0)):
if qx < x - min_d: # out of date, remove
out.append((qy,qx))
else: # check if better
min_d = min(min_d, abs(x-qx)+abs(y-qy))
#
for q in out: py.remove(q)
py.add((y,x))
#
print(min_d)
```
這個程式因為用了動態資料結構，所以超過APCS的範圍，如果用分治演算法就可以避免使用此複雜的資料結構，我們在下一章會介紹。
且慢，這個題目是不是還沒說明完畢？複雜度呢？複雜度其實是$O(n\log n )$，雖然不容易從程式碼中看出來，原因是while迴圈中，如果不計因為X座標太小被刪除的點，每個點計算距離的不會超過8個點！而那些因為X值被刪掉的反正全部的過程中只會被刪一次。為什麼是8點呢？直覺上來看，因為左邊的點之間距離都不小於 $min\_d$，而我們會納入計算的點都落在寬度為$min\_d$高度$2\times min\_d$的矩形內，這樣的點數不可能太多，如果是直線距離，最多6點，如果是$L_1$距離，最多是8點，這並不特別困難，我們留給讀者自己想一想，網路上也可以找到說明。
### 其他習題
---
##### Q-4-16. 賺錢與罰款
泰山派的磨劍坊接了 $n$ 筆訂單，每一筆訂單有需要的工時$t[i]$ 以及完工要求時間 $d[i]$，如果在時間 $x$交貨就可以賺 $d[i]-x$的錢，也就是說越早完成賺越多，超過時間完成的話，越晚賠越多。磨劍坊每次只能做一件工作，所以要把這 $n$ 筆訂單做一個排程，希望利潤最大，也就是賺最多錢，如果不可能賺錢就要賠最少。泰山派掌門天門道長聽到之後，深怕會賠太多的錢而破產，請你幫忙找出最好的排程。
Time limit: 1秒
輸入格式：輸入的第一行是工作數 $n$。第二行有 $n$ 個正整數，依序是各訂單所需時間$t[1],t[2],\ldots,t[n]$。第三行有 $n$ 個非負整數，依序是各訂單的完工要求 $d[1],d[2],\ldots,d[n]$，相鄰以空白間隔。$n<1e5$，花費時間不超過1000，完工要求不超過1e8。
輸出：最大利益。
範例輸入：
5
4 1 5 2 2
2 5 5 3 1
範例結果：
-16
---
---
##### Q-4-17. 死線高手
華山派每個地子都有很多作業，每個作業都有死線(dead-line)，必須在死線之前完成否則會受到處罰。令狐沖現在有 $n$ 個作業，每個作業需要花的時間是 $t[i]$ 而死線是 $d[i]$，此外，每次只能進行一個作業，不可能一次做兩個作業。如果有任何一個作業超過死線，就會被罰到華山之巔面壁一年，請問他是否可能安排作業的順序，讓每個作業的完成時間都不會超過死線，否則小師妹就可能會移情別戀了。
Time limit: 6 秒
輸入格式：輸入包括多筆測資，第一行是測資筆數$T$，$T<20$，以下是 $T$ 筆測資的資料。每筆測資的第一行是作業數 $n$。第二行有$n$個正整數，依序是各作業所需時間$t[1],t[2],\ldots,t[n]$。第三行有n個正整數，依序是各作業的死線$d[1],d[2],\ldots,d[n]$，相鄰以空白間隔。$n<1e5$，時間不超過1000，死線不超過1e8。
輸出：依序輸出每筆測資是否所有作業都可以在死線前完成，是則輸出yes，否則輸出no。
範例輸入：
2
5
2 1 3 1 2
6 6 3 8 9
4
2 1 2 1
3 5 2 6
範例結果：
yes
no
---
下一題跟Q-4-8有關係，是他的變化題。
---
##### Q-4-18. 少林寺的櫃姐 (@@)(\*)
少林寺是觀光勝地，每天要接待很多客人，根據數據分析，方丈決定即使在尖峰時期也必須在時間 $D$內完成$n$個客人的服務，現在的問題是不知道要開設多少個服務櫃台。假設客人依編號順序到達，第$i$個客人需要$t(i)$的時間來完成他的需求(無論分配到哪一個櫃台)，而且每個客人的需求必須在同一個櫃台完成。因為公平的因素，**先到客人的服務開始時間不可以大於晚到客人的服務開始時間**。因為每開設一個櫃台就要請一位櫃姐，為了節省人事成本，請計算出最少要開設多少櫃台才能讓這$n$個客人的服務都在時間$D$內完成。
Time limit: 4秒
輸入格式：輸入兩行，第一行是正整數$n$與$D$，第二行是$n$個正整數$t(1), t(2),…,t(n)$，同行數字間以空白間格。$n$不超過1e5，$t(i)$不超過1e4，$D$不超過1e9也不小於1e4，所以一定有解。
輸出：最少的櫃檯數。
範例輸入：
5 9
3 2 5 7 3
範例結果：
3
---
下一題跟 「P-4-11 線段聯集」有關係。
---
##### Q-4-19. 五嶽盟主的會議場所
武林中一共有$n$個門派，每個門派都要上嵩山去見五嶽劍派盟主左冷禪，每個門派的人數以及到達與停留的時間不盡相同，第$i$個門派有$m(i)$個人要去嵩山，到達時間是$s(i)$，而到達後會一直停留到時間$t(i)$，也就是在嵩山的時間是閉區間$[s(i),t(i)]$。左冷禪需要知道最多會有多少人同時在嵩山，以便準備夠大的會議場所，請計算最多在嵩山的人數。
Time limit: 2 秒
輸入格式：第一行是一個正整數 $n$，接著的$n$行每一行有三個整數，依序是$m(i)$、$s(i)$與$t(i)$，代表一個門派的人數以及到達與最後停留時間，兩者之間以一個空格區隔。n不超過1e5，各派人數不超過1e4，$0 \le s(i) < t(i) \le 1e9$
輸出：依序輸出最多同時在嵩山的人數。
範例輸入：
3
5 1 5
2 5 7
4 8 9
範例結果：
7
---
##### Q-4-20. 監看華山練功場
華山派有$n$個弟子，每個弟子的練功時間都不盡相同，第$i$個弟子到練功場所練功的時間是區間$[s(i),t(i)]$。最近華山頗不平靜，掌門岳不群要求令狐沖找一些弟子練功時順便監看練功場，對於想要監看的時間區間$[x,y]$，請問他最少只要找幾位弟子，這些弟子的練功時間就可以涵蓋整個$[x,y]$。
Time limit: 2秒
輸入格式：第一行是個正整數 $n$，第二行是兩個整數$x$與$y$，接著的$n$行每一行有兩個整數$s(i)$與$t(i)$，同行相鄰兩數之間空白區隔。$n$不超過1e5，$0 \le x < y \le 1e9$， 且對所有$i$，$0 \le s(i) < t(i) \le 1e9$。
輸出：練功時間可以涵蓋$[x,y]$ 的最少的弟子數。如果無解輸出$-1$。
範例一：輸入
5
1 10
0 3
1 5
5 7
8 9
6 10
範例一：正確輸出
3
範例二：輸入
5
1 10
0 3
1 5
5 7
8 9
8 10
範例二：正確輸出
-1
---
**end of chapter 4**
Sign in with Wallet
Connect another wallet