题目链接

题意：给出n个数，求加和大于x的最短区间的区间长度。

如果前i个数字和为y，那么如果前j数字的和小于等于y-x，那么i-j就是一种可能的情况，我们对于所有的i找出前面最大的j就可以了，因为数据量比较大，用树状数组来处理前n项的最大值，但是每个数字又可能比较大，所以先离散化处理一下。

AC代码

1 #include
2 #include
3 #include
4 typedef long long LL;
5
6 using namespace std;
7
8 const double EPS = 1e-8;
9 const int N = 510000;
10 const int INF = 0x3f3f3f3f;
11
12 LL a[N], k;
13 int len;
14
15 struct node
16 {
17 int l; //区间左端
18 LL sum;
19 }p[N];
20
21 void Solve(int l, int r)
22 {
23 LL sum = 0, s = p[r].sum;
24 if(s < k) 25 return ; 26 27 while(l < r) 28 { 29 sum += a[l]; 30 if(s - sum >= k)
31 {
32 p[r].sum = s - sum;
33 p[r].l = l + 1; // 更新区间左端
34 }
35 l++;
36 }
37 len = min(len, r - p[r].l + 1);
38 }
39
40 int main()
41 {
42 int t, n;
43 scanf("%d", &t);
44 while(t--)
45 {
46 memset(a, 0, sizeof(a));
47 memset(p, 0, sizeof(p));
48
49 scanf("%d %lld", &n, &k);
50
51 p[0].l = 1;
52 len = INF;
53
54 for(int i = 1; i <= n; i++) 55 { 56 scanf("%lld", &a[i]); 57 if(p[i-1].sum > 0)
58 {
59 p[i].sum = a[i] + p[i-1].sum;
60 p[i].l = p[i-1].l;
61 }
62 else
63 {
64 p[i].sum = a[i];
65 p[i].l = i;
66 }
67 Solve(p[i].l, i);
68 }
69 if(len == INF) len = -1;
70 printf("%d\n", len);
71 }
72
73 return 0;
74 }

原文出处

UVALive - 6609