UVALive 6609 Minimal Subarray Length(RMQ-ST+二分)
2024-08-23 04:21:49
题意:给定长度为N的数组,求一段连续的元素之和大于等于K,并且让这段元素的长度最小,输出最小长度即可,若不存在这样的元素集合,则输出-1
题目链接: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;
}
最新文章
- python getopt使用
- 【HTML5】浅析HTML5应用程序缓存(ApplicationCache)
- Ubuntu下两个gcc版本切换
- Powerdesigner 16.5 从SQL Server 2012做逆向工程时提示:Unable to list tables问题
- 解决SlidingMenu和SwipeBackLayout右滑事件冲突问题
- asp.net 微信企业号办公系统-流程设计--流程步骤设置-策略设置
- 获取oracle 表字段,表名,以及主键之类等等的信息
- Java中的return
- java 哈希码
- 关于PHP参数的引用传递和值传递
- 将时间显示为“刚刚”“n分钟/小时前”等
- C++ struct 初始化的问题
- 制定一个apk路径 然后跳出安装界面
- 【云计算 Hadoop】Hadoop 版本 生态圈 MapReduce模型
- nacos作为配置中心
- 【bug记录】OS Lab4 踩坑记
- node.js 使用 superagent 与 cheerio 完成简单爬虫
- C语言 sscanf用法详解
- HashSet源码
- STL算法之函数copy