题意
给出一个由n个整数组成的数列，要你求长度最短的连续序列，使得序列中所有元素的和大于等于S。
思路
单调性优化，或者说是尺取法。
暴力O(n^3)显然无法接受，套用前缀和优化再枚举O(n^2)，还是无法接受。
在套用前缀和的基础上，可以枚举终点，二分查找起点，这样是O(nlogn)，可以过了。
然而还有更好的办法，设两个指针，表示连续区间的左端点和右端点，一开始不断右移右端点，直到序列大于等于S，记录长度。然后右移左端点，再开始不断尝试右移右端点，直到条件再次满足，停下纪录，右移一下左端点。。。如此往复，直到右端点无法右移，且左端点无论怎么移动也无法满足条件。
这就是尺取法（名字来源于挑战程序设计竞赛），CF上面也叫Double Pointers，是一种基于单调性的优化手段。
代码
前缀和＋尺取
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> #include <cassert> using namespace std; const int MAXN = 100005; int seq[MAXN]; int sum[MAXN]; int s,n; int solve(){ if(sum[n] < s) return 0; int ret = n; int ptr = 0; for(int i = 1; i<= n; i++){ if(sum[i] >= s){ while(sum[i] - sum[ptr] >= s){ ret = min(ret,i-ptr); ptr++; } } } return ret; } int main(){ while(scanf(" %d %d",&n,&s) != EOF){ for(int i = 1; i <= n; i++){ scanf(" %d",&seq[i]); sum[i] = sum[i-1] + seq[i]; } printf("%d\n",solve()); } return 0; } |
前缀和＋二分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> #include <cassert> using namespace std; const int MAXN = 100005; int seq[MAXN]; int sum[MAXN]; int s,n; int binSearch(int l,int r,int rval){ //right tilted while(l+1<r){ int mid = l + (r-l)/2; if(rval - sum[mid] >= s){ l = mid; }else{ r = mid - 1; } } if(rval - sum[r] >= s){ return r; } return l; } int solve(){ if(sum[n] < s) return 0; int ret = n; for(int i = 1; i<= n; i++){ if(sum[i] >= s){ ret = min(i-binSearch(0,i-1,sum[i]),ret); } } return ret; } int main(){ while(scanf(" %d %d",&n,&s) != EOF){ for(int i = 1; i <= n; i++){ scanf(" %d",&seq[i]); sum[i] = sum[i-1] + seq[i]; } printf("%d\n",solve()); } return 0; } |