题意：给出n个数，求加和大于x的最短区间的区间长度。
如果前i个数字和为y，那么如果前j数字的和小于等于y-x，那么i-j就是一种可能的情况，我们对于所有的i找出前面最大的j就可以了，因为数据量比较大，用树状数组来处理前n项的最大值，但是每个数字又可能比较大，所以先离散化处理一下。
AC代码
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 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 ", len); 71 } 72 73 return 0; 74 }