## b332: 賽伊法則

### 實作模擬題

上面的廢話可以跳過跳到下面。
讀完題目可以發現要做的事情事先模擬一個圓環，每顆鍵會有不同分數由 `a~z` 表示，每次刷鍵有分左右手和順時針逆時針。
首先要做的事情是先把字母換成正常分數。
基本上方法很多，可以拿 `ascii` 碼轉換，或是你直接特判下去也都可以，我個人方法是長這樣。
原理就是 `ascii` 字母會有自己的代碼，在已知只會出現小寫的情況字母會照順序遞增，已知只會出現小寫的情況字母會照順序遞增，然後一個有用的知識是把 `char` 的東西直接強制換成 `int` 會輸出他的 `ascii` 碼，所以只要把現在的字母減掉 `a` 那他現在轉換的數字就會表示是 `a` 後面的第幾個字母，最後只要再加一把數字補回去就完成了。

---

把一開始的分數處理完，接下來就是如何模擬好這題了。
大方向其實很單純：但這題很多人遇到的問題是：手的位置不是每回合都回到 1。(雖然我考試的時候有一直講)
- 初始時兩隻手都是 `1` （`pL=1`、`pR=1`），但每回合結束後，該手的位置要真的往前/往後走 `d` 格（取 `mod 8` ）。
- 得分只算「最多一圈」（`t = min(8, |d|)`），但位置一定要照 d 的真實移動去更新，用 `d%8` 模擬不要真的跑完，不然會吃TLE(有人真的這樣寫)。

---

### 大概流程
1) 準備分數陣列與整圈總和
- 8 顆鍵各自的分數：`val[1..8]`（前面用 ASCII 轉好的那個）
- 一圈總和：`ring_sum = sum(val[1..8])` (方便算)

---

2) 兩隻手的狀態要記三件事（左右手各自獨立）
- 目前位置 `pL / pR`（初始 1）
- 上一次的方向 `dirL / dirR ∈ {-1,0,+1}`（初始 0）
- combo 值 `comboL / comboR`（初始 1）

---

3) 來一回合 (h, d) 怎麼加分
- 如果 `d=0`：本回合加 `0` 分、combo/方向/位置全部不動（就是啥都不要動）
- 否則：
- 方向 `sgn` = `sign(d)`
- 會「踩幾顆」`t = min(8, |d|)`（最多只算一圈的分）
- 從該手「現在的位置」出發，往 `sgn` 方向走 t 步（一步一步加）：
- 注意：起點「當前那格」不計分，第一步是「移動到下一格」才開始算
- 如果 `t==8` （也就是 |d|≥8），這回合分數可以直接拿 `ring_sum`，不用逐格加
- 如果 `t<8`，就真的走 `t` 步、把走到的格子分數加起來
- combo 規則：
- 如果 `sgn` 和該手的 `last_dir` 一樣：combo++
- 否則：`combo=1`，`last_dir=sgn`
- 本回合得分 = 原始路徑分數 × combo
- 最後，該手「位置」要真的移動 `d` 格：
- 位移只需要用 d%8 的等效步數來更新位置：
- ：`mv = ((d % 8) + 8) % 8; pos = int(((pos - 1) + mv) % 8) + 1;`

---

### 為什麼要這樣做
- 「得分只算一圈」是題目限制，但實際上模擬手真的移動了那麼多格，所以「位置」還是要照實際的 `d` 來動。

---

### 小總結
- `d=0`：分數 0、combo/方向/位置全部不動
- |d|≥8：分數直接用 `ring_sum`，但位置還是要照 `d%8` 更新
- 逐步加分時，記得是「先移動再計分」，起點那格不算
- 分數很大，記得用 long long

---

## b265: 同時身為mai眾和vt豚的我，注定是要破產一輩子的(._.`)

題意一句話可以解釋

- 每天要嘛付 `Si = Ai + Bi`，要嘛花一次能力把它壓成 `Mi = min(Ai, Bi)`；最多只能選 K 天用能力。
- 目標讓「最後所有天裡的最大那一天」越小越好。

---

兩種解法(原本我是想出成一定要二分搜，然後考前發現可以用超簡單的純貪心過:P)

#### 本題解中的 Si 表示第 i 天的原始花費，Mi 表示第 i 天用能力後的最低花費

---

### A) 二分搜答案 + 線性檢查
---
- 先建立一個直覺：答案 `M` 其實就是「我希望每天最多能花到多少錢，讓整體都能塞進這個上限裡」，我們要把這個上限壓到最小。
- 做法：先「猜」一個門檻 `T`（例如 `0～max Si` 之間），問自己：「如果規定每天最後都不能超過 `T`，我有沒有辦法在最多 `K` 天使用能力的限制下做到？」
- 檢查的判準（逐天看過去）：
1) 如果某天的「最低可能」`Mi` 都已經大於 `T（Mi > T）`：
- 意思是：「就算我當天用了能力，也壓不進 `T`」→ 這個 T 完全不可能，直接判定不行。
2) 否則，如果「不降的花費」`Si` 大於 `T（Si > T）`而 `Mi ≤ T`：
- 代表：「這一天非降不可」，因為不降就會爆掉。那我就把 need++（表示今天一定要用一次能力）。
3) 如果 `Si ≤ T`：
- 代表今天不降也沒事，就先不降。
- 全部掃完，如果「必須要降的天數 need」不超過 `K（need ≤ K）`→ 代表 `T` 是可行的，反之不可行。
- 為什麼可以二分？因為 T 越大，越容易可行（單調性）。可行區間是一段連續的「大 T」，我們要找最小可行的那個 T。
- 二分邊界怎麼抓?：
- 下界 `lo` = `max_i Mi`（因為每天最小也只能降到 `Mi`，再怎樣 `M` 也不能小於這個）
- 上界 `hi` = `max_i Si`（全部不降時的最大值）
- 具象一點的想法：
- 「今天我把天花板設定在 `T`。」
- 「哪些天就算降也塞不進天花板？」→ `Mi` > `T`（這題 `T` 根本不行）
- 「哪些天不降就會撞到天花板？」→ `Si` > `T`（這些天我非用能力不可）
- 「最後我需要用幾次能力？」→ need
- 「手上次數 `K` 夠不夠？」→ 夠就可行，不夠就不行
- 調整 `T` 再試一次，往「更小的可行 `T`」逼近。
- 一些零碎code：
- `if (Mi > T) return false;`
- `need += (Si > T); // 只要 Si 超過 T，就把它列為必須降一次`
- 這整套邏輯的核心就是：把「複雜的選擇」轉成「只要塞進門檻 T 就算成功」，而塞不進去的那些天就是「必須操作的天」。因為單調性很明顯，二分就會自然收斂到最小可行的 T。

---

### B) 純貪心（最大堆）
- 先把每一天的 `(Si, Mi)` 都存到一個陣列（例如 `vector<pair<long long, long long>> days;`），記下 index。
- 開一個最大堆（`priority_queue<pair<long long,int>>`），把每一天的 `Si` 和 index 丟進去。
- 挑 K 個最大值：每次堆出來看到的就會是 sum 最大的，同時也可以獲得前 `K` 項最大的值的 index 那就再回去 vector 看把那幾項比較大的值減掉，那就會是我們要的最佳策略了。
- 零碎code：「`pq.push({Si, i});`」、`if (pick[i]) ans = max(ans, Mi); else ans = max(ans, Si);`

---

- 看完可能有點卡，另一個更直覺的作法白話點就是說:我先開一個 `vector` 的 `pair` 陣列存每天的兩個值，接著用 `priority_queue` 包 `pair` 一邊存每天的 sum 跟那天的 index 可以很直覺的判斷到，我們使用能力應該要全部使用在總和前 `K` 大的那幾天，這樣存可以很輕易的找到哪幾天要使用能力，再回去把值減掉答案就出來了。再更白話點就是把所有能力丟在最大值那幾天，最後一掃最大值就是答案。

---

### 邊界 tips
- K=0：答案就是 `max Si`
- K=N：答案就是 `max Mi`
- `Si == Mi`：降不降都一樣
- 數值上限到 1e9，記得用 long long

---

### 複雜度
- 二分：O(n log C)（C 大概到 2e9）
- 堆貪心：O(n log n)

---