CF2035E

有兩種操作，第一種代價 \(x\)，第二種 \(y\)。在不能連續進行 \(1\) 操作 \(k\) 次的情況下，問至少需要多少代價才能打出至少 \(z\) 點傷害。

• 使攻擊力 \(d\) 加 \(1\)（初始為 \(0\)）。
• 打出 \(d\) 點傷害。

\(1 \le x, y, z, k \le 10^8\)，\(100\) 組數據。

有一個很顯然的貪心，盡量先第一種再第二種。所以一定是進行 \(c\) 輪 \('k + 1'\) 模式后，再升級 \(r(0 \le r < k)\) 次，最后還需打 \(p\) 次傷害。

可以枚舉 \(c, r\)，計算 \(p_{min}\)。因為 \(c\) 是 \(\sqrt{\frac{z}{k}}\) 級別，所以時間復雜度是 \(O(\sqrt {zk})\)。

然后發現對于每種 \(c\) 都可以整除分塊，只有 \(O(\sqrt k)\) 種 \(p_{min}\)，時間復雜度降為 \(O(\sqrt z + \sqrt k)\)，足以通過。

最開始以為有什么凸性之類的，寫了個二分套三分，然后發現不對，\(10^8\) 的范圍還是指向根號級做法。

不小心對 \(p\) 整除分塊了（有很多種 \(c_{min}\)），搞了挺久的。

當有多種選擇時要仔細分辨，不要盲目隨機選擇。