题目链接

本题是offer收割编程练习赛1的第二题，考察基本的算法和数据结构。

首先我们先来看一下最直接暴力的解法：

我们从1到N枚举缓冲区的大小K，然后计算SP(K)；如果发现SP(K)满足条件，就把当前的K作为答案输出。

function minK()
    for K = 1 .. N
        if(SP(K) <= Q) return K

其中计算SP(K)我们也可以采用O(N^2)最暴力的方法：

function SP(K, P[]) //P[]是输入的数组
    ans = 0
    for i = 1 .. N
        r = min(i+K-1, N)        //缓冲区右边界
        P[x] = max(P[i] .. P[r]) //找到P[i], P[i+1], ... P[r]中最大的P[x]
        swap(P[i], P[x])  
        ans += i * P[i]

以上的方法需要O(N)的复杂度枚举K，以及O(N^2)的复杂度计算SP(K)，总复杂度是O(N^3)的，只能得到很少的分数。

本题优化的方法很多，对应各种不同的复杂度。下面我们来一一分析。

首先可以优化的就是SP(K)。题目要求“每次输出缓冲区中最大的元素”，这是一个典型的最大堆的应用场景。通过用堆优化，我们可以使SP(K)的复杂度降低到O(NlogN)。这样总复杂度可以降低到O(N^2logN)，大概能拿50分。

其次我们可以进一步优化SP(K)。以上我们每个SP(K)都是独立计算的。如果我们知道SP(K)的值，能不能快速求出SP(K+1)的值呢？

事实上是可以的。如果我们仔细观察K逐渐增大时输出的数组，我们会发现它同冒泡排序进行了K-1趟冒泡后的数组是一样的。以样例为例：

5 3 1 2 4
5 3 2 4 1 (K=2)
5 3 4 2 1 (K=3)
5 4 3 2 1 (K=4)

也就是说如果我知道缓冲区大小为K时输出的数组P[]，我只需要对P[]进行一趟冒泡(相邻元素比较交换)即可得到缓冲区大小为K+1时输出的数组。于是我们可以把计算新的SP(K+1)的复杂度降为O(N)。

这样总体复杂度降为O(N^2)，可惜仍然不能得到满分。

想得到满分，我们需要对枚举K进行优化。如果我们对SP的计算公式敏感的话，我们很容易发现随着K增大，SP(K)是单调递减的。（排序不等式？）

于是我们对K进行二分，复杂度O(logN)：

function minK()
    l = 1, r = N, ans = -1
    while(l <= r)
        m = (l + r) / 2
        if(SP(m) <= Q)
            ans = m
            r = m - 1
        else
            l = m + 1
    return ans

由于这时我们计算SP(m)不再是对于从小到大连续的m，所以只能采用堆优化的O(NlogN)复杂度的算法。总体复杂度O(N*logN*logN)，可以得到满分。