网站开发用不用写交互,网站蜘蛛爬行记录,网站怎么换空间,网站专题怎么做呢题目 思路
--刚开始想到暴力尝试的方法#xff0c;但是N太大了#xff0c;第一个测试点都超时。题目中说前k个石头的和还有后k个石头的和要小于s#xff0c;在这里要能想到开一个数组来求前n个石头的总重#xff0c;然后求前k个的直接将sum[i]-sum[i-k-1]就行了#xff0…题目 思路
--刚开始想到暴力尝试的方法但是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;
}
