本文主要是介绍uvalive 6609 - Minimal Subarray Length(离散化+树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出n个数，求加和大于x的最短区间的区间长度。
如果前i个数字和为y，那么如果前j数字的和小于等于y-x，那么i-j就是一种可能的情况，我们对于所有的i找出前面最大的j就可以了，因为数据量比较大，用树状数组来处理前n项的最大值，但是每个数字又可能比较大，所以先离散化处理一下。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 500005;
int id[MAXN];
map<ll, int> s;
map<ll, int>::iterator p;
int c[MAXN * 2];
void update(int u, int d, int m) {while(u <= m) {c[u] = max(c[u], d);u += u & -u;}
}
int query(int u) {int ans = -1;while(u) {ans = max(c[u], ans);u -= u & -u;}return ans;
}
int main() {int t, n, m, i, j, x, a;scanf("%d", &t);while(t--) {s.clear();scanf("%d%d", &n, &x);for(i = 1; i <= n; i++)scanf("%d", &id[i]);memset(c, -1, sizeof(c));s[0] = 0;ll sum = 0;for(i = 1; i <= n; i++ ){sum += id[i];s[sum] = 0;s[sum - x] = 0;}m = 0;for(p = s.begin(); p != s.end(); p++)p->second = ++m;a = s[0];update(a, 0, m);sum = 0;int tmp, ans = -1;for(i = 1; i <= n; i++) {sum += id[i];tmp = query(s[sum - x]);update(s[sum], i, m);if(tmp == -1) continue;if(ans == -1 || i - tmp < ans)ans = i - tmp;}printf("%d\n", ans);}return 0;
}
这篇关于uvalive 6609 - Minimal Subarray Length(离散化+树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
