本题题意：
有个长度为n的数组，问是否存在区间能让区间内部数字和大于k （要求区间尽可能短）
第一行输入 n k
之后输入数组
最终输出最短的区间长度
这道题我们可以用二分法解决，时间大概是 O(nlogn)即一次全部遍历和一次二分搜索
有了之前几道题的竟然。。这道解决的也更加快了建议先自己想一下
代码如下
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int a[1e8 + 10]; int n, s; void slove(){ int sum = 0; for (int i = 0; i < n; i++) { //记录一个前缀和 sum += a[i]; a[i] = sum; } int res = n + 1; for (int i = 0; a[i] + s <= a[n - 1]; i++) { int tmp = lower_bound(a + i, a + n, a[i] + s) - a - i; //调用函数 // lower_bound 是一个封装好的函数，会返回里搜索值最近的较大的数 res = min(res, tmp); } if (res == n + 1)printf("0\n"); else printf("%d\n", res); } int main() { int t; scanf("%d", &t); while (t--) { memset(a, 0, sizeof(a)); scanf("%d%d", &n, &s); for (int i = 0; i < n; i++) scanf("%d", a[i] ); slove(); } return 0; }
当然 还有一种更加优秀的算法 我们叫它 尺取法（因为这种算法很像一种虫子蠕动的感觉，貌似因为尺蠖这种虫子音译的原因）
想象我们构造一个滑动区间（类似于一个可以推动的玻璃门）这个区间内的数字之后如果大于 s 那么这个区间就是成立的然后记录区间长度并且比较。至于怎么去确保这个区间滑动同时里边数字和大于 s 我们就采用那种虫子蠕动的思想:
上边界持续增长 ，直到大于S
下边界开始收缩 ，直到小于S
最后记录 每个 Up-Down 的值 比较出最大 就是这种思想了。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int s,e; int t,n,k; const int maxn = 1e8+5; int num[maxn]; int main() { cin>>t; while(t--) { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>num[i]; } s=e=1; int sum=0; int res=n+1; for(;;)//构造一个死循环 { while(e<=n&&sum<k)//开始把上边界增长 //就像虫子蠕动时头先向前伸出去 { sum+=num[e]; e++; } if(sum<k)break;//如果走到了头就结束 res=min(res,e-s);//记录最短区间 sum-=num[s++];//然后增长下边界 //像虫子蠕动的时候尾部再向回收缩 } if(res>n)res=0; cout<<res<<endl; } return 0; }
