<题目链接>
题目大意：
给你一段长度为n的整数序列，并且给出一个整数S,问你这段序列中区间之和大于等于S的最短区间长度是多少。
解题分析：
本题可以用二分答案做，先求出前缀和，然后枚举区间长度，然后再判断其是否合法即可，复杂度$O(nlog(n))$。同时，尺取法也是一个不错的选择，通过不断的移动区间的头、尾指针来寻求答案，复杂度为 $O(n)$。
尺取法：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int n,s,val[int(1e5+)]; int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&s);
for(int i=;i<=n;i++)scanf("%d",&val[i]);
int sum=,l=,r=;
int ans=1e9;
while(true){ //推进区间的头结点和尾节点
while(sum<s && r<=n)sum+=val[r++];
if(sum<s)break;
ans=min(ans,r-l);
sum-=val[l++];
}
if(ans==1e9)puts("");
else printf("%d\n",ans);
}
}
尺取法
二分答案：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 1e5+;
int n,s;
int sum[N];
bool check(int x){ //判断是否有符合条件的区间
for(int i=;i+x-<=n;i++){
if(sum[i+x-]-sum[i-]>=s)return true;
}return false;
}
int main(){
int T;scanf("%d",&T);while(T--){
sum[]=;
scanf("%d%d",&n,&s);
for(int i=;i<=n;i++)
scanf("%d",&sum[i]),sum[i]+=sum[i-];
int l=,r=n,ans=-;
while(l<=r){ //二分答案，枚举区间长度
int mid=l+r>>;
if(check(mid))ans=mid,r=mid-;
else l=mid+;
}
if(ans==-)puts("");
else printf("%d\n",ans);
}
}
二分答案
2019-03-03