Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/problemset/problem/279/B 题意：给定一个序列，问一段连续的序列的和小于等于t的最长的序列的长度。 思路：尺取法。三个月前学习的了。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月15日 星期二 20时08分16秒
4File Name :code/cf/problem/279B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34int n;
35int t;
36int a[N];
37
38void solve()
39{
40 int head = 1;
41 int tail = 1;
42 int sum = 0 ;
43 int ans = 0 ;
44 while (tail<=n)
45 {
46// cout<<"aaaaa?"<<endl;
47 sum = sum + a[tail];
48// cout<<"head:"<<head<<" tail:"<<tail<<" sum:"<<sum<<endl;
49 if (sum>t)
50 {
51 while (sum>t)
52 {
53 sum = sum - a[head];
54// cout<<"sum:"<<sum<<endl;
55 head++;
56 }
57 }
58 if (sum<=t)
59 ans = max(ans,tail-head+1);
60 tail++;
61
62 }
63 printf("%d\n",ans);
64}
65int main()
66{
67 #ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69 #endif
70
71 scanf("%d%d",&n,&t);
72 for ( int i =1 ; i <= n ; i++) scanf("%d",&a[i]);
73 solve();
74
75 #ifndef ONLINE_JUDGE
76 fclose(stdin);
77 #endif
78 return 0;
79}