hihocoder 136周

题目就不贴了，是关于冒泡排序的，贴一波大神分析：

本题是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)复杂度的算法。总体复杂度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分，不过自己验证是没错的。
本题学到：当单调递增或递减时，用二分法比从头到尾查找复杂度要低，还有要会用数学归纳法。