https://www.cnblogs.com/violet-acmer/p/9793209.html
马上就要去上课了，先献上二分AC代码，其余的有空再补
题意：
给定长度为 n 的整数数列 a[0,1,2,........,n]以及整数 S。
求出总和不小于 S 的连续子序列的长度的最小值。
如果解不存在，则输出 0。
题解：
1、二分
由于所有的元素都大于 0 ，所以数组a[ ] 的前缀和sum[ ]为递增的序列，满足二分的条件。
首先确定子序列的起点为start(start的可能取值为 1,2,......,n)。
假设区间[start,end]是以start为子序列起点的最小区间，则需要满足 sum[end]-sum[start-1] >= S，而确定满足条件的最小的 end 用二分即可在O(longn)的时间完成。
所以总的时间复杂度为 O(nlogn)
2、尺取法
相关说明：
设以a[start]为子序列起点的总和最初大于S的连续子序列为a[start,......,end]，此时 res = end-start+1;
(1):end++，找到最大的 k ，使得在去除当前子序列的前 k 个数后依旧满足 sum[end]-sum[start-1 + k] >= S，并判断是否需要更新 res。
(2):重复(2)过程，直到 end > n 为止。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mem(a,b) (memset(a,b,sizeof(a)))
const int maxn=1e5+; int N,S;
int a[maxn];
int sum[maxn];
int binarySearch(int val)
{
int l=,r=N+;
while(r-l > )
{
int mid=l+((r-l)>>);
if(sum[mid] >= val)
r=mid;
else
l=mid;
}
return r;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
mem(sum,);
scanf("%d%d",&N,&S);
int res=;
for(int i=;i <= N;++i)
{
scanf("%d",a+i);
sum[i] += sum[i-]+a[i];
}
for(int s=;s <= N;++s)
{
int t=binarySearch(sum[s-]+S);
if(t != N+)
res=(res== || (t-s+)<res ? t-s+:res);
}
printf("%d\n",res);
}
}
二分
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define pb push
const int maxn=1e5+; int N,S;
int a[maxn];
queue<int >myqueue; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
while(!myqueue.empty())
myqueue.pop();
scanf("%d%d",&N,&S);
for(int i=;i <= N;++i)
scanf("%d",a+i);
int end=;
int sum=;
int res=;
while(sum < S && end <= N)//先找到以1为序列起点的满足条件的最小的end
{
sum += a[end];
res++;
myqueue.pb(a[end++]);
}
if(sum >= S)
{
while(sum-myqueue.front() >= S)//找到满足条件的当前最小的范围
{
sum -= myqueue.front();
myqueue.pop();
res--;
}
while(end <= N)
{
myqueue.pb(a[end]);
sum += a[end++];
while(sum-myqueue.front() >= S)//步骤(2)
{
sum -= myqueue.front();
myqueue.pop();
}
res= res > myqueue.size() ? myqueue.size():res;//判断是否更新 res
}
}
else
res=;
printf("%d\n",res);
}
}
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1e5+; int N,S;
int a[maxn]; int Solve()
{
int start=,end=;
int res=;
int sum=;
while()
{
while(end <= N && sum < S)
sum += a[end++];
if(sum < S)
break;
res=(res == || (end-start) < res ? end-start:res);
sum -= a[start++];
}
return res;
} int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&S);
for(int i=;i <= N;++i)
scanf("%d",a+i);
printf("%d\n",Solve());
}
}
尺取法&挑战程序设计竞赛