# TIOJ 1337 隕石 & Greedy + Binary Search + Discretization 筆記
###### tags: `tutorial` `解題筆記` `TIOJ` `Greedy` `Binary Search` `Discretization`

:::warning
每天都要解題。
[題目在這裡呦。](https://tioj.ck.tp.edu.tw/problems/1337)
[參考資料](https://polarzcoding.blogspot.com/2017/09/tioj1337.html)，作者很弱所以只好照著做囉。
:::

---

## Greedy 貪進法

對於每一個情況，都做對當下最有利的選擇（能拿多少就拿多少），在某些題目的條件下，這樣的做法就可以保證有最佳解。
> 例如：
> 以新台幣換零錢時，每一次都從最大面額的開始換；當一個面額無法再換時，再換成下一個面額的錢幣。如此，便可以保證換到的錢幣數量最少。

不一定每題都可以使用貪進法，能夠使用（不能使用）的情形也可以證明。但是作者不會證，所以我會說，「只要知道什麼時候可以用就好。」

以本題為例：
> 假設可以用 $P$ 個防護罩，
> 我們可以從左到右（這是習慣，只要方向固定即可）依序掃描。
> 如果有一個點 $X_i$ 會被超過 $P$ 個隕石打到，
> 就把「會打到那個點的所有隕石」之中「攻擊範圍右界最右邊的」打掉，
> 直到會打到 $X_i$ 的隕石數量等於 $P$ 。
> 這樣就是最佳解囉。
> 同樣的，作者也不會證，請自行看範測參透囉。

> 複雜度：$O(n)$ 。

---

## Binary Search 二分搜

對於一個長度為 $n$ 單調序列 $a$ ，想要尋找 $k$ 時，可以先設搜尋的左界 $L$ 和右界 $R$ （一開始常設為頭）尾，再依據中間項 $a_M\ ,\ M = \frac{(L + R)}{2}$ 與 $k$ 比較結果決定縮小 $L$ 或 $R$ ，可以把搜尋的複雜度降到 $O(\log_2 n)$ 。

以本題為例：
> 隨著可以使用防護罩數 $P$ 遞增，
> 需要打掉的隕石數 $K$ 必會遞減，
> 這樣就符合單調的條件。
> 因此，我們可以使用二分搜，
> 搜尋最小的 $P$ 使其有符合題目的 $K$。

> 複雜度：$O(\log_2 n)$ 。

---

## Discretization 離散化

:::info
[參考資料。](https://zhuanlan.zhihu.com/p/85776198)
特別感謝電神學長提供。
:::

當一個題目值域太大，且數值又很稀疏的時候，可以使用離散化使值域縮小。

以本題為例：
> 若今天有兩顆隕石 $A(0,65536)$ 跟 $B(10,62830)$，
> 線性跑完就要從$0$跑到$65536$。
> 而且題目的值域是 $-10^9$ ～ $10^9$，
> 線性就直接爆了。
> 用了離散化之後，兩顆隕石的座標可以變成
> $A(0,3)$ 跟 $B(1,2)$ ，
> 這樣不但不會影響相對順序，
> 還可以減少運算需要時間喔。

概念請看上面的參考資料喔。

> 複雜度：$O(n\log n)$ 。

---
## 實作囉

首先是 Greedy，給定 $P$ 跟 $K$，判斷是否可行。

再來是 Binary Search，二分搜尋 $P$。

最後是 Discretization，讓常數不會爆掉。