首页 > 代码库 > UVALive 6609 Minimal Subarray Length（RMQ-ST+二分）
UVALive 6609 Minimal Subarray Length（RMQ-ST+二分）
题意：给定长度为N的数组，求一段连续的元素之和大于等于K，并且让这段元素的长度最小，输出最小长度即可。
题目链接：UVAlive 6609
做法：做一个前缀和prefix，然后再作一个维护前缀和最大值数组Max，枚举所有可能的起始点i，在Max上二分末尾位置r，由于Max维护的是前缀和的最大值，因此具有单调性，可以进行二分，似乎还有其他O（n）的做法，有空去膜一下
代码：
#include <stdio.h>#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 500010;LL arr[N];LL Max[N][20];LL prefix[N];void init(){ CLR(Max, -0x3f3f3f3f3f3f3f3f); prefix[0] = 0LL;}void RMQ_init(int l, int r){ int i, j; for (i = l; i <= r; ++i) Max[i][0] = max<LL>(Max[i][0], prefix[i]); for (j = 1; l + (1 << j) - 1 <= r; ++j) { for (i = l; i + (1 << j) - 1 <= r; ++i) { Max[i][j] = max<LL>(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]); } }}LL ST(int l, int r){ int k = log2(r - l + 1); return max<LL>(Max[l][k], Max[r - (1 << k) + 1][k]);}int main(void){ int tcase, n, i; LL k; scanf("%d", &tcase); while (tcase--) { init(); scanf("%d%lld", &n, &k); for (i = 1; i <= n; ++i) { scanf("%lld", &arr[i]); prefix[i] = prefix[i - 1] + arr[i]; } RMQ_init(1, n); int ans = INF; for (i = 1; i <= n; ++i) { int L = i, R = n; int temp = -1; while (L <= R) { int mid = (L + R) >> 1; LL Get = ST(i, mid); if (Get - prefix[i - 1] >= k) { temp = mid; R = mid - 1; } else L = mid + 1; } if (~temp) ans = min(ans, temp - i + 1); } printf("%d\n", ans == INF ? -1 : ans); } return 0;}UVALive 6609 Minimal Subarray Length（RMQ-ST+二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。