[AtCoder] [經典競程 90 題] 001 - Yokan Party（★4）

最近一直覺得自己該復健一下。剛好看到這系列，決定來寫一下回復一下手感，順便練練日文，不然真的太久太久沒自己好好做題了，什麼都忘光光了 😥

---

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_a
題目大意:
有一個 $L$ 公分的羊羹，其中有 $N$ 個可以切的地方，從左數來第 $i$ 個可以切的位置在 $A_i$ 公分。你要選擇切 $K$ 刀使得產生 $K+1$ 塊的羊羹出來。定義切完後的羊羹的分數為： 切出來的 $K+1$ 塊中長度最小塊的長度。我們想要最大化切出來的分數。答案請輸出最大可能的分數。

---

挺經典的二分搜題，跟骨牌遊戲 那種題目有點類似，可以直接對答案二分搜。假設我們知道分數是 $x$ ，那就代表只要當前位置與上一刀距離超過 $x$ 就可以砍一刀下去，而如果砍了 $K$ 刀的話就可以停下來，且代表這個分數是達的到的。根據這件事情我們就可以二分搜出最大的分數 $x$ 使得還可以砍得出 $K$ 刀。
惹..講得有點模糊，但 code 短短的可能可以看一下它 (?)

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, d, k; cin >> n >> d >> k;
	vector<int> a(n);
	for (int &a_i : a) cin >> a_i;

	auto valid = [&] (int m) {
		int piv = 0, tot = 0;
		for (int a_i: a) {
			if (a_i - piv >= m and d - a_i >= m) {
				tot++;
				piv = a_i;
			}
		}
		return tot >= k;
	};

	int l = 0, r = 1'000'000'001;
	while (r - l > 1) {
		int m = (l + r) >> 1;
		if (valid(m)) l = m;
		else r = m;
	}
	cout << l << '\n';
	return 0;
}