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

本題是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 45 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)復雜度的算法?？傮w復雜度O(N*logN*logN)，可以得到滿分。
===================================================================
我自己一開始用的是暴力解法，只得了40分，而且結果是Runtime Error，后續還會根據大神的分析改進一下。
改進了一般的代碼：
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的最小值還沒改進，只改進了用K的SP值求出K+1時的SP值，但是提交還是RE，40分，不過自己驗證是沒錯的。
本題學到：當單調遞增或遞減時，用二分法比從頭到尾查找復雜度要低，還有要會用數學歸納法。