7.28 二分+尺取+复杂度

本文主要是介绍7.28 二分+尺取+复杂度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.二分

定义：是一种非常高效的搜索方法，主要原理是每次搜索可以抛弃一半的值来缩小范围。。
问题
什么时候我们可以大致判定该题需要用到二分法？
(1). 需要对一道时间复杂度为n的题目进行优化；
(2). 在题目中提到的数组已排序；
(3). 只搜索一个值或一个位置

代码实现（时间复杂度log(n)）
int l=1,r=n;
while (l <=r){
int mid =(l+r )/2;
if(a[mid ]== x){
return mid ;
} else if(a[mid]>x){
r=mid -1;
} else {
l=mid +1;
}
}
return -1;
upper_bound lower_bound

2.尺取

2.1定义：顾名思义，像尺子一样取一段，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不
断地推进区间左右端点以得出答案。（之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区
间效率高很多，尤其是数据量大的）

2.2问题:
什么情况下能使用尺取法？
何时推进区间的端点？
如何推进区间的端点？
何时结束区间的枚举？

2.3样例：

给定长度为n的数列整数a0，a1，a2....an-1以及整数S。

求出总和不小于S的连续子序列的长度的最小值。

如果不存在，则输出0
n=10,S=15,a={5,1,3,5,10,7,4,9,2,8};
第一次(5 1 3 5 10) 7 4 9 2 8
第二次5 (1 3 5 10) 7 4 9 2 8
第三次5 1 (3 5 10) 7 4 9 2 8
第四次5 1 3 (5 10) 7 4 9 2 8
第五次5 1 3 5 (10 7) 4 9 2 8
第六次5 1 3 5 10 (7 4 9) 2 8
第七次5 1 3 5 10 7 (4 9 2) 8
第八次5 1 3 5 10 7 4 (9 2 8)

2.4整个过程分为四步
1初始化左右端点
2不断扩大右端点，直到满足条件
3如果第二步中无法满足条件，则终止，否则更新结果
4 将左端点扩大，然后回到第二步
用尺取法优化使复杂度将为O(n)

//白书P148
#include <cstdio>
#include <algorithm>
#include<iostream>
using namespace std;
//const int INF = 0x7fffffff;//long int的最大值
const int MAXN = 100000+5;
int a[MAXN];
int n, s;void solve()
{//尺取法int l = 0, r = 0;   //初始化左右指针int sum = 0, res =n+1;//sum为子序列的和，res为子序列长度 for(;;){while(r < n && sum < s)//不断移动右指针，直到满足条件{   sum += a[r++];}if(sum < s) //条件无法满足，终止break;res = min(res, r-l);    //更新结果，相应区间为[l, r)，右减左sum -= a[l++];  //移动左指针}//printf("%d\n", res >n ? 0 : res);//解不存在，输出0 cout<<(res >n ? 0 : res)<<endl;
}int main()
{int t;scanf("%d", &t);while(t--){cin>>n>>s;//n为序列总长度 for(int i = 0; i < n; ++i)cin>>a[i];solve();}return 0;
}