Description
A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.
Input
The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.
Output
For each the case the program has to print the result on separate line of the output file.if no answer, print 0.
Sample Input
2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5Sample Output
2 3题意是让你找一个最小的连续序列，他们的和大于m。
预处理前缀和，二分枚举序列的长度。
AC Code：
#include<iostream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #include<deque> #include<set> #include<bitset> #include<cctype> #define LL long long #define maxn (LL)1e6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define pb push_back #define re register LL const double eps = 0.0000001; using namespace std; typedef pair<LL,LL> pii; inline int sgn(double x) { return (x > eps) - (x < -eps); } int Sum[maxn]; int ans[maxn]; int n,m; bool judge(LL idx) { for(re i =1;i<=n-idx+1;i++) { if(Sum[i+idx-1] - Sum[i-1]>=m) return 1; } return 0; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE int T; cin>>T; while(T--) { cin>>n>>m; for(re i = 1;i<=n;++i) { cin>>ans[i]; Sum[i] = Sum[i-1] + ans[i]; } if(Sum[n]<m) { cout<<0<<endl; continue; } LL L = 1,R = n; while(L<R) { LL mid = (L+R)/2; if(judge(mid)) R = mid; else L = mid + 1; } cout<<R<<endl; } }原来two pointers思想就是尺取啊，学习了，很巧妙。
尺取法；应用于有这么一类问题，需要在给的一组数据中找到不大于某一个上限的“最优连续子序列”
AC Code：
#include<iostream> #include<iomanip> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #include<vector> #include<map> #include<stack> #include<queue> #include<deque> #include<set> #include<bitset> #include<cctype> #define LL long long #define maxn (LL)1e6 #define INF 0x3f3f3f3f #define PI acos(-1.0) #define pb push_back #define re register LL const double eps = 0.0000001; using namespace std; typedef pair<LL,LL> pii; inline int sgn(double x) { return (x > eps) - (x < -eps); } int ans[maxn]; int n,m; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE int T; cin>>T; while(T--) { cin>>n>>m; for(re i = 1;i<=n;++i) { cin>>ans[i]; } int res,sum = 0;//ans 为答案 ，sum存序列的和 int _s = 1,_e = 1; //两个指针 ，起点和终点 res = maxn; while(1) { while(sum<m&&_e<=n)//先寻找到大于m的区间 { sum+=ans[_e++]; } if(sum<m) break;//检查剩余序列是否小于m res = min(res,_e - _s);//更新答案 sum -= ans[_s++];//尝试缩短区间，起点后移 } if(res == maxn){ cout<<0<<endl; } else cout<<res<<endl; } }
