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 |
#include <iostream> #include <sstream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; int sum[100005]; inline int gettime(int from,int to){ return sum[to] - sum[from-1]; } int main(){ ios_base::sync_with_stdio(false); int n = 0,t = 0; while (cin >> n >> t) { memset(sum, 0, sizeof(sum)); for (int i = 1; i <= n; i++) { int tmp = 0; cin >> tmp; sum[i] = sum[i-1] + tmp; } int res = 0; for (int i = 1; i <= n; i++) { int *pos = lower_bound(sum+1, sum+n+1, sum[i-1]+t); int tmp = pos - sum; if (*pos - sum[i-1] != t) { tmp--; } tmp-=i-1; res = max(res,tmp); } cout << res << 'n'; } return 0; } |
lower_bound真的不是那么好掌握的。。。有时候很坑。
这个题就是前缀和还不够,在前缀和的基础上还要使用二分搜索进一步减小时间复杂度才能过掉大数据。