題目地址:

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

暴力法超時(shí)

大概意思給出腿長(zhǎng)和每個(gè)階梯的高度差，求出該腿長(zhǎng)下能達(dá)到最大的高度。

看完題目后，估計(jì)大家心想: 這么簡(jiǎn)單還放在E題?

一開(kāi)始想法直接暴力模擬, 為什么暴力呢? 我們只需要迭代高度差并比較腿長(zhǎng), 直接將算出最高的高度, 這樣的算法復(fù)雜度才O(n)， 值得賭一手:

看到測(cè)試用例一直都正確通過(guò)，心里還是挺開(kāi)心的，結(jié)果到了test5，超時(shí)。。。

二分查找答案

我們先用前綴和的方法求出樓的總高度, 假設(shè)前綴和數(shù)組為b, 那么不管腿長(zhǎng)為多少, 答案的范圍必定在[0,?b[-1]]之間.

既然答案的范圍都找到了，不然想到用二分法去搜索，這樣算法復(fù)雜度會(huì)降到O(nlogn)。

如何搜索呢? 我們將問(wèn)題轉(zhuǎn)化, 對(duì)于腿長(zhǎng)K, 我們需要在a1,...,ai中找到下標(biāo)i使得ai <= k (這里的ai是a1,...,ai的最大值)

我們需要新建另一個(gè)數(shù)組m, 滿足mi = max(a1, ..., ai), 于是mi <= k。接下來(lái)我們可以用二分搜索找到這個(gè)索引i, 輸出b[i]就是我們的答案了

本題貌似還滿足最優(yōu)子結(jié)構(gòu), 本蒟蒻還在想一種dp解法, 可惜太弱沒(méi)把狀態(tài)方程找出來(lái)。。