题意:给定长度为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;
}

最新文章

  1. python getopt使用
  2. 【HTML5】浅析HTML5应用程序缓存(ApplicationCache)
  3. Ubuntu下两个gcc版本切换
  4. Powerdesigner 16.5 从SQL Server 2012做逆向工程时提示:Unable to list tables问题
  5. 解决SlidingMenu和SwipeBackLayout右滑事件冲突问题
  6. asp.net 微信企业号办公系统-流程设计--流程步骤设置-策略设置
  7. 获取oracle 表字段,表名,以及主键之类等等的信息
  8. Java中的return
  9. java 哈希码
  10. 关于PHP参数的引用传递和值传递
  11. 将时间显示为“刚刚”“n分钟/小时前”等
  12. C++ struct 初始化的问题
  13. 制定一个apk路径 然后跳出安装界面
  14. 【云计算 Hadoop】Hadoop 版本 生态圈 MapReduce模型
  15. nacos作为配置中心
  16. 【bug记录】OS Lab4 踩坑记
  17. node.js 使用 superagent 与 cheerio 完成简单爬虫
  18. C语言 sscanf用法详解
  19. HashSet源码
  20. STL算法之函数copy

热门文章

  1. 2018.5.25 Oracle相关的函数命令
  2. Virtuabox 虚拟机克隆方法
  3. Java反射得到属性的值和设置属性的值
  4. sudo apt-get install ubuntu-desktop, Error: unable to locate package
  5. C#进阶之全面解析Lambda表达式
  6. 博学谷-数据分析numpy
  7. vue切换路由时动画
  8. Oracle数据库学习(四)
  9. Ansible指令和常用模块使用
  10. 进入docker容器并执行命令的的3中方法