題目就不貼了，是關(guān)于冒泡排序的，貼一波大神分析：

本題是offer收割編程練習(xí)賽1的第二題，考察基本的算法和數(shù)據(jù)結(jié)構(gòu)。

首先我們先來看一下最直接暴力的解法：

我們從1到N枚舉緩沖區(qū)的大小K，然后計(jì)算SP(K)；如果發(fā)現(xiàn)SP(K)滿足條件，就把當(dāng)前的K作為答案輸出。

function minK()    for K = 1 .. N        if(SP(K) <= Q) return K
其中計(jì)算SP(K)我們也可以采用O(N^2)最暴力的方法：
function SP(K, P[]) //P[]是輸入的數(shù)組    ans = 0    for i = 1 .. N        r = min(i+K-1, N)        //緩沖區(qū)右邊界        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)的復(fù)雜度枚舉K，以及O(N^2)的復(fù)雜度計(jì)算SP(K)，總復(fù)雜度是O(N^3)的，只能得到很少的分?jǐn)?shù)。
本題優(yōu)化的方法很多，對(duì)應(yīng)各種不同的復(fù)雜度。下面我們來一一分析。
首先可以優(yōu)化的就是SP(K)。題目要求“每次輸出緩沖區(qū)中最大的元素”，這是一個(gè)典型的最大堆的應(yīng)用場(chǎng)景。通過用堆優(yōu)化，我們可以使SP(K)的復(fù)雜度降低到O(NlogN)。這樣總復(fù)雜度可以降低到O(N^2logN)，大概能拿50分。
其次我們可以進(jìn)一步優(yōu)化SP(K)。以上我們每個(gè)SP(K)都是獨(dú)立計(jì)算的。如果我們知道SP(K)的值，能不能快速求出SP(K+1)的值呢？
事實(shí)上是可以的。如果我們仔細(xì)觀察K逐漸增大時(shí)輸出的數(shù)組，我們會(huì)發(fā)現(xiàn)它同冒泡排序進(jìn)行了K-1趟冒泡后的數(shù)組是一樣的。以樣例為例：
5 3 1 2 45 3 2 4 1 (K=2)5 3 4 2 1 (K=3)5 4 3 2 1 (K=4)
也就是說如果我知道緩沖區(qū)大小為K時(shí)輸出的數(shù)組P[]，我只需要對(duì)P[]進(jìn)行一趟冒泡(相鄰元素比較交換)即可得到緩沖區(qū)大小為K+1時(shí)輸出的數(shù)組。于是我們可以把計(jì)算新的SP(K+1)的復(fù)雜度降為O(N)。
這樣總體復(fù)雜度降為O(N^2)，可惜仍然不能得到滿分。
想得到滿分，我們需要對(duì)枚舉K進(jìn)行優(yōu)化。如果我們對(duì)SP的計(jì)算公式敏感的話，我們很容易發(fā)現(xiàn)隨著K增大，SP(K)是單調(diào)遞減的。（排序不等式？）
于是我們對(duì)K進(jìn)行二分，復(fù)雜度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
由于這時(shí)我們計(jì)算SP(m)不再是對(duì)于從小到大連續(xù)的m，所以只能采用堆優(yōu)化的O(NlogN)復(fù)雜度的算法。總體復(fù)雜度O(N*logN*logN)，可以得到滿分。
===================================================================
我自己一開始用的是暴力解法，只得了40分，而且結(jié)果是Runtime Error，后續(xù)還會(huì)根據(jù)大神的分析改進(jìn)一下。
改進(jìn)了一般的代碼：
import java.io.*;import java.util.*;public class Main {	public static void main(String args[]) {		int n = 0;		int q = 0;		int k = 1;		Scanner scan = new Scanner(System.in);		n = scan.nextInt();		q = scan.nextInt();		int[] a = new int[n];		//int[] c = new int[n];		int[] b = new int[n];		scan.nextLine();		for(int i = 0; i < n; i ++) {			a[i] = scan.nextInt();		}		if(mul(a) <= q) {				System.out.PRint(1);				System.exit(1);			} 		for(k = 2; ; k ++) {			if(k == n + 1) {				System.out.print(-1);				break;			}			if(k > 2) {				for(int i = 0; i < n - 1; i ++) {					if(b[i] < b[i+1]) {						int temp = b[i];						b[i] = b[i+1];						b[i+1] = temp;					}				}				if(mul(b) <= q) {				System.out.print(k);				break;					} else {continue;}			}			for(int i = 0; i < n - k + 1; i ++) {								for(int j = i + 1; j < i + k; j ++) {					if(i == 1) {						}					b[i] = a[i];					if(a[j] > a[i]) {						b[i] = a[j];						a[j] = a[i];						a[i] = b[i];					}				}			}			for(int i = n - k + 1; i < n; i ++) {				b[i] = a[i];				for(int j = i + 1; j < n; j ++) {					if(a[j] > a[i]) {							b[i] = a[j];							a[j] = a[i];						a[i] = b[i];					}				}			}			if(mul(b) <= q) {				System.out.print(k);				break;			}		}	}	public static int mul(int[] a) {		int r = 0;		for(int i = 0; i < a.length; i ++) {				r += (i + 1) * a[i];			}		return r;	}	}二分法查找K的最小值還沒改進(jìn)，只改進(jìn)了用K的SP值求出K+1時(shí)的SP值，但是提交還是RE，40分，不過自己驗(yàn)證是沒錯(cuò)的。
本題學(xué)到：當(dāng)單調(diào)遞增或遞減時(shí)，用二分法比從頭到尾查找復(fù)雜度要低，還有要會(huì)用數(shù)學(xué)歸納法。