题目地址:

https://codeforces.com/problemset/problem/1742/E

暴力法超时

大概意思给出腿长和每个阶梯的高度差，求出该腿长下能达到最大的高度。

看完题目后，估计大家心想: 这么简单还放在E题?

一开始想法直接暴力模拟, 为什么暴力呢? 我们只需要迭代高度差并比较腿长, 直接将算出最高的高度, 这样的算法复杂度才O(n)， 值得赌一手:

看到测试用例一直都正确通过，心里还是挺开心的，结果到了test5，超时。。。

二分查找答案

我们先用前缀和的方法求出楼的总高度, 假设前缀和数组为b, 那么不管腿长为多少, 答案的范围必定在[0, b[-1]]之间.

既然答案的范围都找到了，不然想到用二分法去搜索，这样算法复杂度会降到O(nlogn)。

如何搜索呢? 我们将问题转化, 对于腿长K, 我们需要在a1,...,ai中找到下标i使得ai <= k (这里的ai是a1,...,ai的最大值)

我们需要新建另一个数组m, 满足mi = max(a1, ..., ai), 于是mi <= k。接下来我们可以用二分搜索找到这个索引i, 输出b[i]就是我们的答案了

本题貌似还满足最优子结构, 本蒟蒻还在想一种dp解法, 可惜太弱没把状态方程找出来。。