蓝桥杯-礼物-二分查找

题目

思路

--刚开始想到暴力尝试的方法，但是N太大了，第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s，在这里要能想到开一个数组来求前n个石头的总重，然后求前k个的直接将sum[i]-sum[i-k-1]就行了，这样就不用再加个循环求和了，直接相减，降低了时间复杂度。题目中是让求k的，而这个k可以取值的条件与k在数组中的位置有关。可以从1到n/2范围遍历，当然时间复杂度比较大，换用二分查找。二分查找可以遍历每一种可能的k值，并且时间复杂度较小。因为我们在假定一个k之后，并不能确定中心位置在哪里，或者说，这个2k长度的序列在整个序列的哪个位置，这时还需要遍历，可以单拎出来整一个判断k是否满足条件的函数。

--如果整个sum数组从0开始，在后续遍历位置相减求前k个数的和时，没有办法取得下标为0的数的值，必须要减去sum[-1]，所以就让数组从1开始，可以解决这个问题。

--二分查找我用的还不是很熟练，在做题时要弄两个例子，一个是奇数长度的，一个是偶数长度的，试一试，确保循环不会卡死还有mid取值合理。

代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;long long n, s;
long long sum[1000001]; //表示当前所有石头的重量和。
int k = 0; bool chazhao(int mid){for (long long i = mid; i + mid <= n; i++){if (sum[i] - sum[i - mid] <= s && sum[i + mid] - sum[i] <= s){return true;}}return false;
} //寻找符合条件的mid，这里的mid = k，也就是在寻找合适的k。因为并不确定n的奇偶性。 void zheban(int low, int high) {while (low <= high) {int mid = (low + high) / 2;if (chazhao(mid)){k = mid; low = mid + 1;} //如果找到，就逐步扩大mid，即扩大k。 else{high = mid - 1;} //如果没有找到，就缩小k。 }
}int main(){cin >> n >> s; sum[0] = 0;for (int i = 1; i <= n; i++){int w;cin >> w;sum[i] = w + sum[i - 1];}zheban(1, n); //折半查找k。 cout << k * 2 << endl;return 0;
}