本文主要是介绍蓝桥杯-礼物-二分查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
思路
--刚开始想到暴力尝试的方法,但是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;
}
这篇关于蓝桥杯-礼物-二分查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!